235 views
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 | 235 views
0
**********
+1
$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
+1
I'm getting O($n^{2}$). Is it correct?
+1
@hemant yes you are corrrect.I made a mistake , solved now
0
I am getting O($n^{2} log n$)
+1
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
0
And as k is depedent on j, so only iteration of k will be counted  and iteration of j will not count
0
@Ahwaan @srestha

Kindly check my comment on the answer to this question. I hope the explanation  makes sense.
0
@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.

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
0
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 ?
0
yes $n*n$
0
@sourav

I have got some problem in ur ans

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

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

k=0,1,2

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

k=0,1,2

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

k=0,1,2

k=0,1,2,3,4

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

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

@rishi @sourav

for i loop each n times

inner loops (logn + n) ~= n

therfore n2

am i right in my approach

0

@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

$1+2+4+8+...2^h$

0
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
0
there is no statement ,then how you calculating complexity
0
yes some time it depend on statement

But not always statement matters

As statement not given, we may think , it is statement independent
+2
@Srestha

Why are you doing like this?

--------------------------------------------------------

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

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

k=0,1,2

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

k=0,1,2

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

k=0,1,2

k=0,1,2,3,4

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.
0

@A_i_s_h,

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 . .. $2^{x}$ 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}$)

0

@rishi

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

can u elaborate this part

0
$2^{x} = n$

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

@rishi

+1 vote