Big O Notation of an example

Question

My professor gave this example in a lecture:

Example: Given an integer N, print out the values 1…N.

for (int i=1; i<=N; i=i+1) { System.out.print(i); }

The professor said that the loop was O(n) because it printed the values 1 to N. However I thought that Big O Notation was a reference to the amount of items in the input data therefore it would be O(1) (which is technically equivalent to O(n) as the input size is 1) due to it only accessing a single data item once.

Am I right in thinking this?

Answer 1

Your argument is totally wrong in an interesting way.

The time used is proportional to N. The input is N. But what is the size of N? For a 32 bit integer the size is 32 bits. For a 64 bit integer the size is 64 bits. For a k bit integer with a size of k bits, the value N can be as large as 2^k (almost) so the time isn't O (1) in the size of the input, but O (2^k) if the input has a size of k bits.

Answer 2

You've got two things going on here - You have a loop (the for statement) and you've got the inner statement of the loop (System.out.print(i);).

for (int i=1; i<=N; i=i+1) { 
    System.out.print(i); 
}

You want to start at the inner and work out. For this, System.out.print(i); is considered O(1) - you're doing a fixed amount of work.

for (int i=1; i<=N; i=i+1) { 
    System.out.print(i); //<-- O(1)
}

Next we look at the loop - this executes N times, making it O(N). You then multiply this times the inner statement, giving you O(1) * O(N) - which is O(N).

for (int i=1; i<=N; i=i+1) { //<-- O(N)
    System.out.print(i); //<-- O(1)
}

The thing to remember here is that your input is N, not i. You could do 3 things inside your loop, but since they are all fixed cost, you still consider them O(1)

for (int i=1; i<=N; i=i+1) { // <-- this is still O(N)
    int g = i * i;       //
    int g /= 2;          // <-- This is all still considered O(1) because N isn't involved.
    System.out.print(g); //
}

Answer 3

Complexity is said to be O(1) only when the statements of that function f(n) are not affected by the factor 'n'.

For example, the complexity of the following C# algorithm is 'O(1)' even if it prints something 90,00,000 times which implies to O(9000000) in turn it is O(1).

Regardless of 'n' being 0, 1000, 10000000,... the function, 'OrderOnOneFunction(n)' prints the 90 lacs lines in the output console.

public void OrderOnOneFunction(int n)
{
    Console.WriteLine("One");
    Console.WriteLine("Two");
    Console.WriteLine("Three");
    Console.WriteLine("Four");
    Console.WriteLine("Five");
    Console.WriteLine("Six");
    Console.WriteLine("Seven");
    Console.WriteLine("Eight");
    Console.WriteLine("Nine");
    //...
    //...
    //...
    Console.WriteLine("Ninety Lacs");
}