Do the arithmetic operations really execute in constant time?

ABSTRACT

The paper emphasizes the need for exposing the undergraduate computer science students to the bit-level analysis of the run-times of certain computer algorithms. These are algorithms where the input(s) consist of one or more integers and only a bit-level analysis yields a more realistic estimate of the run-time behaviors of such algorithms.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Rosen, K. Elementary Number Theory and its Applications (4th edition), Addison Wesley, 2000.
• 3: Neal Koblitz, A course in number theory and cryptography, Springer-Verlag New York, Inc., New York, NY, 1987
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001