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

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