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

asked in Algorithms by Junior (913 points)
edited by | 208 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+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)$

answered by Veteran (15.6k 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$
@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..............

@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

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

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

@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}$)

 

 

@rishi

 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 :)

 @rishi

Related questions

0 votes
1 answer
1
asked in Algorithms by Sonali Rangwani Active (1.3k points) | 68 views
0 votes
1 answer
2
asked in Algorithms by jatinmittal199510 Active (1.8k points) | 68 views
0 votes
0 answers
3


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

29,167 questions
36,992 answers
92,219 comments
34,837 users