Question

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

Answer 1

An input size of N = 128 makes the algorithm run for 14 milliseconds

Step-by-step explanation:

O(log2N)

This means that the running time for an algorithm of length N is given by:

`F(N) = clog_2(N)`

In which C is a constant.

Runs for 10 milliseconds when the input size (N) is 32.

This means that
`F(32) = 10`

So

`F(N) = clog_2(N)`

`10 = clog_2(32)`

Since
`2^5 = 32, log_2(32) = 5`

Then

`5c = 10`

`c = (10)/(5)`

`c = 2`

Thus:

`F(N) = 2log_2(N)`

What input size makes the algorithm run for 14 milliseconds

N for which
`F(N) = 14`. So

`F(N) = 2log_2(N)`

`14 = 2log_2(N)`

`log_2(N) = 7`

`2^(log_2(N)) = 2^7`

`N = 128`

An input size of N = 128 makes the algorithm run for 14 milliseconds