i want to calculate the complexity of the following code snippet

``````for(int k=0;k<n; ++k)
for(int j=0; j<k; ++j)
for(int i=0; i<j; ++i)
cout<< "Hello World" <<endl;``````

here! i got the hint! that summation of natural numbers series would be used if its correct why ?

4
Contributors
4
Replies
5
Views
11 Years
Discussion Span
Last Post by Infarction

Try out this simple code snippet:

``````int main (void)
{
const int LIMIT = 4 ;
int counter_I = 0, counter_J = 0, counter_K = 0 ;
int i, j, k ;

for ( i = 0; i < LIMIT; ++ i )
{
++ counter_I ;
for ( j = 0; j <= i; ++ j )
{
++ counter_J ;
for ( k = 0; k <= j ; ++ k )
{
++ counter_K ;
}
}
}
printf ( "\nThe value of counter i is %d ", counter_I ) ;
printf ( "\nThe value of counter j is %d ", counter_J  ) ;
printf ( "\nThe value of counter k is %d ", counter_K ) ;
printf ( "\nThe value of counter is %d ", counter_I + counter_J + counter_K ) ;

return 0 ;
}``````

Thus the total times is:

Outermost loop = 4
Middle Loop = 4 + 6
InnerMost loop = 4 + 6 + 10

Hope you see the pattern.

Thank You ~S.o.S~ & Ancient Dragon for your help finally i learn how to calculate the polynomial complexity.....

``````for( int i=0; i<n; ++i )
for( int j=0; j<i; ++j )
printf("Hello World");``````

if we consider the inner loop the complexity ...

In the above loop int i=0; is an atomic statement which executes O(1) time i.e. constant time.
i<n executes (n+1) times
++i executes (n+1) times

printf(“Hello World”); //executes n times

so the total complexity is 1 + (n+1) + (n+1) + n = 3n+3

and the complexity of the ourter loop would be ...
For(int i=0; i < n; ++i )
{
//something executes 3n+3 times………….
}
lets examine the outer loop,

int i=0; //executes 1 time
i < n; //executes n+1 times\
++i //executes n+1 times.
And last the body executes ?? interesting………….
See………….
First i=0;
Complexity of body is 3(0)+3
i=1
Complexity of body is 3(1)+3
i=2
Complexity of body is 3(2)+3
i=3
Complexity of body is 3(4)+3
………………………………
……………………………….
i=n
Complexity of body is 3(n)+3

Therefore, total complexity is equal to

1 + (n+1) + (n+1) + [ {3(0)+3} + {3(1) + 3} + ………… + { 3(n) + 3} ]..
1 + (n+1) + (n+!) + [3(0 + 1 + 2 + 3 + … + n) + 3n] //using 1 + 2 + … + n = n(n+2)/2
1 + (n+1) + (n+1) + [3(n(n+2)/2) + 3n]
1 + (n+1) + (n+1) + 3n + 3(n(n+1)/2)
so, total complexity after solving……..
3 + 5n + 3n2/2 + 3n/2 ...............:p , hope i understand the mathematics behind ,...................
m i right gurus?

No. Unless 3n2/2 is supposed to mean (3n^2)/2, which is something of a deduction...

Let's work this out from the inside out, starting with `printf("Hello World");` . This'll execute in (approx.) constant time.

Now we've got a loop. This loop will execute i times (0 to i-1). For each iteration of the loop, we'll execute the inner statement, which we noted is constant. Overall our time is a linear function of i, which we'll approximate as being i and drop anything else.

Now we've got another loop. This loop will execute n times, coincidentally providing the limit for the inner loop. The maximum limit for the inner loop is also n, and we'll use this in a second. So the outer loop executes n times, and for each iteration of that loop the inner one will execute as well, according to its own conditions. We can approximate that the inner loop will execute n times for each iteration of the outer loop. So, for each iteration of the outer loop, there's n iterations of the inner loop. There's n iterations of the outer loop. That's a total of n^2 iterations of the printf(), which would be O(n^2) in big-O notation. If you need the exact complexity, you'll have to work through it again tracking the details.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.