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

Answer:

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

Explanation:

O(log2N)

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

$F(N) = c\log_{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) = c\log_{2}{N}$

$10 = c\log_{2}{32}$

Since $2^5 = 32, \log_{2}{32} = 5$

Then

$5c = 10$

$c = \frac{10}{5}$

$c = 2$

Thus:

$F(N) = 2\log_{2}{N}$

What input size makes the algorithm run for 14 milliseconds

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

$F(N) = 2\log_{2}{N}$

$14 = 2\log_{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