0

Hi eveyone :)
I am having trouble understanding some big o notation that i have been given in homework. I have tried reading my text books but nothing makes sense to me well. Below is one of the problems i have been given

#include <stdio.h>

int main()
{
    int i, inner_count = 0, n = 40000;

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

    printf("Inner statement executed %d times\n", count);

    return 0;
}

Is the running time of this code expressed as O(n)??? I'm pretty sure its not because of the n * n part of the for loop

Your help would be greatly appreciated :)

Edited by WaltP: n/a

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by Narue
0

>Is the running time of this code expressed as O(n)???
Well, n is your base count, and the loop always multiplies that by itself. The behavior is really no different from this:

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

Which is obviously O(n^2).

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.