Lower bounds for computations with the floor operation

TY - JOUR

T1 - Lower bounds for computations with the floor operation

AU - Mansour, Yishay

AU - Schieber, Baruch

AU - Tiwari, Prasoon

PY - 1991

Y1 - 1991

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0026140431

UR - https://www.scopus.com/pages/publications/0026140431#tab=citedBy

U2 - 10.1137/0220020

DO - 10.1137/0220020

M3 - Article

SN - 0097-5397

VL - 20

SP - 315

EP - 327

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -