Big o notation runtime

Question

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

one more i didn't see and have absolutely no idea with {

    int i, wrong_count = 0, n = 200;

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

    printf("%d %d\n", wrong_count, square(wrong_count));

    return 0;
}

int square(int m)
{
    int i, j = 0;

    for(i = 0; i < m * m; i++)
    {
        j++;
    }

    return j;
}

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

Cheers

Answer 1

• number5 is O(N^2)
• number6 is O(N^6)
• number7 is O(N*logN)
• number8 is O(logN)

the rest seems correct.

Try to understand how many operations are done as function of N, all the constant operation, such as

for (int i = 0; i < 333333333; ++i) { j++; } 

are in fact O(1)

Answer 2

number5 = O(n^2) -- the 2nd loop goes from 1 to a number less than n, including n, so it's basically 1..n, or O(n).

number6 = O(n^6) -- the 2nd loop is n^2 and the 3rd is n^3 (n*n^2). The 4th, inner loop is o(1) so it doesnt count.

number7 = O(n log n) -- the first loop is o(log2(n)) (because you keep dividing the index by 2) and the 2nd loop is o(n) 1..n, and the inner loop is again o(1) because it doesn't depend on n.

number8 = o(log n) -- same reason as above.

the rest are fine.

Answer 3

Your answers to 5, 6, 7, and 8 are incorrect if my quick traces are right.
below is a trace of 8

1: int i, j, pseudo_inner_count = 0, n = 1073741824;
2: 
3: for(i = n; i > 1; i /= 2)
4: {
5:     pseudo_inner_count++;
6:     for(j = 0; j < 50000000; j++);
7: }

so, line 5 is a prim op and thus O(1) same with the checking and assignment in line 3. line 6 looks like it's going to be something big, but because it's always going to be 50000000, it's a constant time operation of O(1) as well, that leaves us with this shell to consider:

1: int i, j, pseudo_inner_count = 0, n = 1073741824;
2: 
3: for(i = n; i > 1; i /= 2)
4: {
5: }

I'm not in the business of doing someone's homework for free but I'll finish this one off, the method of reducing i is that of division of two meaning it will take about log_2 operations to reach 1, giving a runtime of O( log( n ) )