The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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?

asked in Algorithms by Active (1.1k points)
edited by | 226 views
$O\left ( nlog^{3}n \right )$
As first for loop goes upto n iterations
2nd for loop goes upto log n iterations
3rd for loop goes upto $\left ( log n \right )^{2}$ iterations
I'm getting O($n^{2}$). Is it correct?
@hemant yes you are corrrect.I made a mistake , solved now
I am getting O($n^{2} log n$)
Why so much discussion on this? Outer loop is independent. Multiply O(n) at last. Analyze inner two step by step, you will get O(n).... now multiply. You get O(n^2).  This is an easy question. I guess some people are misreading the second loop. i.e     for ( j=1;j<n ; j=j*2)   ... It is  j<n ....not j<i
And as k is depedent on j, so only iteration of k will be counted  and iteration of j will not count
@Ahwaan @srestha

Kindly check my comment on the answer to this question. I hope the explanation  makes sense.
@srestha Iteration for j is already counted when we take one by one values of j and say what happens to k....   @rishi yes O(n sq)  and it was in GP too.

1 Answer

+3 votes
Best answer

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=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)$

answered by Veteran (17.7k points)
selected by
Okay, so iterations of 3rd loop (innermost) covers the iteration of 2 nd loop.

And the outer most loop has no relation with any of inner most loop. That is time complexity = n * timeComplexity of inner loops.

Is it ?
yes $n*n$

I have got some problem in ur ans

Say, i=1 -> j=1  -> k=0,1

i=2 ->j=1,2 -> k=0,1


i=3 ->j=1,2 -> k=0,1


i=4 ->j=1,2,4-> k=0,1



So, j will not run only 1,2,4............

but it will run like 1,2,2,4..............

@rishi @sourav

for i loop each n times

inner loops (logn + n) ~= n

therfore n2

am i right in my approach

@Sreshtha :first of all you do not bother about outermost loop,they have no any relation with 2nd and 3rd loop.


Now see carefully the innermost loop -:

for ( k=0;k<j ;k++)

let us write the above snippet as-:

for ( k=1;k<=j ;k++)

Now see k is running for every value of j.

j=1,k will run 1 times

j=2, k will run 2 times

j=4, k will run 4 times

j=8,k will run 8 times


see the pattern


But outer most loop also take a part for calculating inner two loops

and that is why k will take log n complexity and not n
there is no statement ,then how you calculating complexity
yes some time it depend on statement

But not always statement matters

As statement not given, we may think , it is statement independent

Why are you doing like this?


Say, i=1 -> j=1  -> k=0,1

i=2 ->j=1,2 -> k=0,1


i=3 ->j=1,2 -> k=0,1


i=4 ->j=1,2,4-> k=0,1



So, j will not run only 1,2,4............

but it will run like 1,2,2,4..............

'j' is independent of 'i'. j <n is there and not j<i.


Lets forget about the outer loop for a while.

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


Number of Outer Loop Iteration 0th 1st 2nd 3rd . . . xth iteration
value of j 1 2 4 8 .. . n
Number of times inner loop runs 1 time 2 times 4 times 8 times . ..



Now, we are concerned only about the number of times inner loop runs, which is a GP of powers of 2. = $2^{x+1}-1$

Now how is x nd n related ? $2^{x} = n$

Therefore, $2^{x+1}-1$ = 2n - 1 = O(n)

Now bring in the outer loop, which runs n times irrespective of any of the inner loop. Therefore, net time complexity  = O($n^{2}$)




 2x+1−1 = 2n - 1 = O(n)

can u elaborate this part

$2^{x} = n$

$2^{x+1}-1 = (2*2^{x})-1 = (2*n)-1$
tanku :)


Related questions

+1 vote
0 answers
asked in Algorithms by ashish pal Active (1.3k points) | 30 views
+2 votes
0 answers
+2 votes
0 answers
asked in Algorithms by smsubham Boss (5.5k points) | 46 views

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,712 questions
40,255 answers
38,881 users