Lower bounds for computations with the floor operation

Research output: Contribution to journalArticle

16 Scopus citations


A general lower bound technique is developed for computation trees with various arithmetic operations and constants {0, 1}, for functions that have as their input a a single n-bit integer. The technique applies to many natural functions. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with the given operations that solves the problem.

Original languageEnglish (US)
Pages (from-to)315-327
Number of pages13
JournalSIAM Journal on Computing
Issue number2
StatePublished - Jan 1 1991
Externally publishedYes


All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science(all)

Cite this