MadeEasy Subject Test 2019: Algorithms - Time Complexity

Question

1. O($n^2$)
2. O(n)
3. O(nlogn)
4. O($n(logn)^2$

 

Comments

yes answer  is b

---

Ohkkk

---

Can't we say like this for larger values of $n$ the term $(\frac{1}{2})^(log n)$ tends to zero and hence $O(n)$

Answer 1

When i = n , inner query runs for n times ,

now i = n/2 inner query runs n/2 times ,

now i = n/4 inner query runs for n/4 times ,

So the total number of steps the inner query would run is

n + n/2 + n/4 + n/8 + n/16 + ....... for exactly log(n) times .

 take n common

n(1+1/2+1/4+1/8+1/16.... ) = n (2 - 1/2^(logn))  = n (2 - 1/n) , lets take  n approaches infinity ,

1/n approaches 0.

Therefore , complexity = O(2n) = O(n)

Comments

Why Time complexity is not depending on outer loop ?

I mean the outer for loop i.e. 'i' runs for log n times and the inner for loop i.e. 'j' runs for n times, so ain't the answer should be O(n*logn). ?