Big o notation runtime

Posted by mrblippy on Stack Overflow See other posts from Stack Overflow or by mrblippy
Published on 2010-03-18T08:04:18Z Indexed on 2010/03/18 8:11 UTC
Read the original article Hit count: 180

Filed under:
|

Hi, i have been given some code to work out big o runtimes on them, could someone tell me if i am on the right track or not??

//program1
 int i, count = 0, n = 20000;

for(i = 0; i < n * n; i++)
{
    count++;
}

Is that O(n^2)???

//number2
int i, inner_count = 0, n = 2000000000;

    for(i = 0; i < n; i++)
    {
        inner_count++;
    }

is this one O(n)????

    //number3
for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            count++;
        }
    }

O(n^2)?????

//number4
for(i = 0; i < n; i++)
    {
        for(j = 0; j < i; j++)
        {
            for(k = 0; k < j; k++)
            {
                inner_count++;
            }
        }
    }

is that O(n^3)?????

//number5
int i, j, inner_count = 0, n = 30000;

    for(i = 0; i < n; i++)
    {
        for(j = 0; j < i; j++)
        {
            inner_count++;
        }
    }

is that one O(n^3)?

//number6
int i, j, k, l, pseudo_inner_count = 0, n = 25;

    for(i = 0; i < n; i++)
    {
        for(j = 0; j < i*i; j++)
        {
            for(k = 0; k < i*j; k++)
            {
                pseudo_inner_count++;
                for(l = 0; l < 10; l++);
            }
        }
    }

very confused about this one O(n^3)??

//number7

int i, j, k, pseudo_inner_count = 0, n = 16;

    for(i = n; i > 1; i /= 2)
    {
        for(j = 0; j < n; j++)
        {
            pseudo_inner_count++;
            for(k = 0; k < 50000000; k++);
        }
    }

o(n)???? (i get more lost as they get harder)

//number8
int i, j, pseudo_inner_count = 0, n = 1073741824;

    for(i = n; i > 1; i /= 2)
    {
        pseudo_inner_count++;
        for(j = 0; j < 50000000; j++);
    }

O(n^2)???

If anyone could clarify these and help me understand them better i would be very grateful

-cheers

© Stack Overflow or respective owner

Related posts about c

    Related posts about homework