Question

Suppose that an algorithm has run-time proportional to 2ⁿ , where n is the input size. The algorithm takes 1 millisecond to process an array of size 10. How many milliseconds would you expect the algorithm take to process an array of size 20 ?

Answer 1

algorithm has runtime of 2"

$\frac{t1}{t2}=\frac{n1}{n2}$

$\frac{t1}{t2}=\frac{2^{20}}{2^{10}}=2^{10}=1024$

$so,\;t1=1024*t2$

$given\;t2=1millisecond$

$t1=1024\;milliseconds=1.024\;seconds$

$\color{Red}Answer:=1.024\;seconds$

$Note:\;\;if\;runtime\;is\;2n\;instead\;of\;2^n\;then\;answer\;is\;2\;milliseconds.$