CODEWITHSUNDEEP
algorithmbig-oanalysis
banna
banna

Reputation: 165

Big O Notation: For loop with O(1) operation on the inside

I'm working on understanding big O notation a little bit better and got stumped on this problem in class.

If I had a for loop with a constant number of iterations that simply prints something to the console on each iteration:

for(int i=1; i<10; i++)
{
   cout << "Hello!" << endl; 
}

What would the big O notation for this snippet of code be? The line that writes to the console takes 1 unit of time, and I would multiply this by the number of times it would be executed - in this case 10 - so I would get O(10). However, this just reduces to O(1).

Is this a correct analysis?

Upvotes: 2

Views: 677

Answers (1)

Y.T.
Y.T.

Reputation: 2768

Even for a loop like this:

for (int i = 0; i < 1000000; i++) {
  cout << i << '\n';
}

It's technically still O(1). I am not going to go through the formal definition of Big O notation here. But in simple words, big O notation measures how fast the running time grows with respect to input. In this case, the theoretical runtime should be the same no matter what the input is. (in fact there isn't even input). So your analysis is correct.

Upvotes: 3

Related Questions