The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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?

$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

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

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

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

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 ?

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 ?

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

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 n^{2}

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

and that is why k will take log n complexity and not n

yes some time it depend on statement

But not always statement matters

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

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.

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 398
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,712 questions

40,255 answers

114,368 comments

38,885 users