Question

Assume that an O(log2N) algorithm runs for 10 milliseconds when the input size (N) is 32. What is input size makes the algorithm run for 14 milliseconds?

Answer 1

Assume F(n) is the function for the run time of an algorithm.

Then, F(n) = c log₂n for some constant say c.

F(32) = c log₂32 = 10

=> 5c = 10, Hence c = 2

Similarly,

F(n) = 2 log₂n = 14, Hence log₂n = 7

=> n = 2⁷= 128

Therefore, the input size which makes the algorithm run for 14 milliseconds is 128 (N).