1

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?

3

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.

  • The problem here is that O notation is not meant to be used in specific contexts where you know the size of the array - it's a generalized formula that is meant to compare algorithms at a broad scale. For example, we reduce O(N^2) + O(N) to just O(N^2). Why? Because for sufficiently large N's, the O(N) is irrelevant. If you are limiting yourself to only 32 or even 64 bit sized N's, you're already getting away from the point of Big O notation at all. – Ampt Jan 29 '16 at 17:43
  • 32 and 64 bit was an example. – gnasher729 Jan 29 '16 at 23:14
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); //
}
  • 1
    I think the OP's question is not whether the loop has n or i or 1 iterations, but whether the n we use in the expression O(n) is meant to be the value of the input or the size of the input, which is a much more interesting question. Relevant: en.wikipedia.org/wiki/Pseudo-polynomial_time – Ixrec Jan 29 '16 at 16:24
0

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");
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.