edited by
1,025 views
4 votes
4 votes
for (i=n ; i>0 ; i--)
    {
    for ( j=1;j<n ; j=j*2)
        {  
        for ( k=0;k<j ;k++)
            {
            
            }
            
        }
        
    }


time complexity ??
how to find of inner and innermost loop?

edited by

1 Answer

Best answer
4 votes
4 votes

Outermost loop will run for $n$ times , will not effect $2^{nd}$ and $3^{rd}$ loop.

outermost loop will run for $n$times


$j=1\rightarrow k=1$

$j=2 \rightarrow k=1,2$

$j=4\rightarrow k=1,2,3,4$

$j=8\rightarrow k=1,2,3,4,5,6,7,8$

$\vdots \vdots$

$j=n\rightarrow k=1,2,3,4,5,6,7,8.....2^h$


k will run -:

3rd loop$=2^0+2^1+2^2+.....2^h$

$=2^{h+1}-1$

$2^h=n\Rightarrow h=\log n$

3rd loop$=2^{\log n +1}-1=n^{\log 2} \times 2-1\approx n$

Outermost loop will run $n$times

Overall time complexity=$\Theta (n^2)$

selected by

Related questions

1 votes
1 votes
2 answers
1
akankshadewangan24 asked Sep 20, 2018
841 views
If t(n) and s(n) denotes the time and space complexity of an algorithm with input size n element then which one of the following is always true?S(n)=O(t(n)) correct H...
0 votes
0 votes
3 answers
2
Subham Nagar asked Mar 20, 2018
1,179 views
An array $'A'$ has $n$ distinct integers. What is the tightest time complexity to check $A[i]=i$ for some $i$. Consider all elements of array within range from $1$ to $n$...
0 votes
0 votes
0 answers
3
Kai asked Jan 29, 2017
422 views
Time complexity of the given program is?
1 votes
1 votes
1 answer
4