Algorithms Basic Question

Question

Comments

is it O(n)...??

---

But how????

---

$\begin{align*} \text{complexity =} \sum_{k=1}^{\log n} \left [ \frac{n}{2^k} \right ] = O(n) \end{align*}$

Answer 1

Here we have to look at the total iterations that take place to check the running time  - 

The outer i will change as N , N/2 , N/4 ,...

the inner j will loop equal to the value of i.

thus Total iterations = n + n/2 + n/4 +....

Now use geometric mean = a * (1 - r^k) / (1 - r). 

                                     = N * (1 - (1/2) ^ logn ) / (1 - 1/2)  = 2n - 2.                 

 [ k = total no of terms = logn , as N is continuously being divided by 2]

Thus T(n) = O(n)