Ace Test Series: Algorithms - Time Complexity

Question

Comments

@ air1ankit

n(2⁰+2¹+2²+......) logn times(becoz second loop is running logn times)  :-  n(2^logn-1)  :-   O(n²)

---

@hs_yadav thanks, but i wants to know about for loop of k , ????

---

@ air1ankit

k loop is exicuting to value of ....for evry single excution j loop ...k loop is exicuting j times...means 

when

j=1 k-1 times

j=2  k-2 times.

j=2²  k-2²   

......

......logn times...therefor it is going to be....(2⁰+2¹+2²+......) 

Answer 1

i loop is executing $\Theta(n)$ times.

j loop is executing $\Theta(\log n)$ times for each i. (So, time complexity must for code must be $\Omega(n \log n)$

But it is not straight forward to count the no of iterations of k loop as it depends on the value of j. So, we can see the values of j which goes like 1, 2, 4, ... n. So, no. of iterations of k loop (over all j values) will be $\sum_{j=0}^{\lg n} 2^j = 2^{\lg n +1} =  \Theta(n)$. And this is over all j loops (not including i). Including i loop we get time complexity as $\Theta\left(n^2 \right).$

Comments

Thank you @Arjun Sir