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

I believe that's just factorial...and insanity. http://www.cppreference.com/wiki/complexity

Your compiler would also probably just simplify that as:

printf("Inner statement executed 160000000 times\n");

PS: We have an edit button, you don't have to make a second thread.

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.