Lower bounds for computations with the floor operation

Research output: Contribution to journalArticle

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

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science(all)

Cite this