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

    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

8 Years
Discussion Span
Last Post by Narue

>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++) {

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.