madeesay work book

Question

An algorithm processes an input of size n if n=4,096 and the run time=512 milliseconds. If n=16,384, run time is 8,192 MS. What is the efficiency in big O notation?

O(n^1/2)

O(n)

O(n^2)

O(nlogN)

Comments

is the answer $C\,\,\,(O(n^{2}))$

Answer 1

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)

 

 

Comments

What is the reason of assuming : "Suppose the time complexity of the given algorithm is T(n) = O(n^k₁ log^k₂n)."

why not only n^k₁ ??????????

why not only log^k₂n ?????????/

---

@eyeamgj : by taking nlog n form, we can cover all the options for comparison. the solution is not unique i think, so you can take any form anyways.

---

ok