Lower bounds for computations with the floor operation

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

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
Volume20
Issue number2
DOIs
StatePublished - Jan 1 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

Cite this