Lower bounds for computations with the floor operation

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Research output: Contribution to journalArticlepeer-review

17 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 - 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Lower bounds for computations with the floor operation'. Together they form a unique fingerprint.

Cite this