Dark Mode

1,738 views

1 vote

Suppose the time complexity of the given algorithm is $T(n)$ $=$ $O(n^{k1}$$log^{k2}n)$.

Substituting the given values, we get two equations as,

$512 ms = 4096^{k1} log^{k2}(4096)$

ie; $512 ms = 4096^{k1}$ x $12^{k2}$ ............ (1)

and $8192 ms = 16384^{k1} log^{k2}(16384)$

ie; $8192 ms = 16384^{k1}$ x $14^{k2}$ ........... (2)

Now $\frac{(1)}{(2)}$ gives,

$\frac{512 ms}{8192 ms} =$ $\frac{4096^{k1}}{16384^{k1}}$ x $\frac{12^{k2}}{14^{k2}}$

Or, $\frac{1}{16} =$ ($\frac{1}{4})^{k1}$ $(\frac{12}{14})^{k2}$

Let's compare $k1$ and $k2$ in the given choices and if it satisfies the above equation:

(A) $O(n^\frac{1}{2}) \Rightarrow$ k1 = $\frac{1}{2}$; k2 = $0$ => Doesn't Satisfy

(B) $O(n) \Rightarrow$ k1 = $1$; k2 = $0$ => Doesn't Satisfy

(C) $O(n^2) \Rightarrow$ k1 = $2$; k2 = $0$ => $Satisfies$

(D) $O(n log n) \Rightarrow$ k1 = $1$; k2 = $1$ => Doesn't Satisfy

Or you can go directly as : The equation is satisfied when $k1=2$ and $k2=0$.

So the complexity is given by $O(n^2 log^0n) = O(n^2)$

So the answer is** (C)**

0

0