retagged by
794 views
2 votes
2 votes

retagged by

1 Answer

Best answer
6 votes
6 votes

Outermost loop having $i$ as iterator executes $O(n)$ time. (No doubt here)

Let's decode other two loops $\Rightarrow$

for(j=1;j<n;j*=2) {
    for(k=0;k<j;k++)
}

When $j= 1$, Innermost loop executes 1-time.
When $j = 2$, Innermost loop executes 2-times.
When $j = 4$, Innermost loop exexutes 4-times.

So, total number of times innermost loop executes $= 1+2+4 + \dots + 2^k = \frac{2^{k+1} -1}{2-1} = 2^{k+1} -1$

And condition j < n evaluates to be false when $2^{k+1}-1 \ge n$, thus $k = O(\log_2n)$

So, Overall time complexity $= O(n) * O(2^{k+1}-1) = n*O(2^{\log_2n}) = O(n^2)$

selected by

Related questions

0 votes
0 votes
2 answers
1
Gate Fever asked Sep 27, 2018
1,987 views
0 votes
0 votes
1 answer
2
0 votes
0 votes
3 answers
3
1 votes
1 votes
2 answers
4
srestha asked Aug 17, 2018
1,055 views
What will be TC here?Ans given $O(n^{2})$ , while I am getting $O(n)$