Comlexity of algorithm

[Laiq Ahmed]

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 ?
bit confused:sad:

[~s.o.s~]

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.

[Ancient Dragon]

I think what you want to read is this thread.

[Laiq Ahmed]

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?

[Infarction]

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.