What is the Big O Notation of a nested loop where the inner loop is ran a fixed number of times regardless of N?

StackOverflow https://stackoverflow.com/questions/16204754

  •  11-04-2022
  •  | 
  •  

Question

function DoStuff(someNumber) {
    for(var i = 1; i <= someNumber; i++) {
        // some arbitrary logic
        for(var a = 0; a <= 3; a++) { // This loop gets run 4 times regardless of i
            // Do something 
        }
    }
}

Is the BigO notation of this method O(n) + 4 and therefore just O(n)?

Was it helpful?

Solution

It is O(n), here's why:

The inner loop is executed N times (where N is "someNumber" in your code). It, of course, causes 4 executions. This does NOT mean that your program is O(n) + 4, as you suggested (that is not proper syntax for big O notation anyway, you meant either O(n+4) or O(n) + O(4)). It means your program is O(4*n). When one loop is nested in another, you multiply the two bounds of those loops. That is, if the outer loop goes till M and the inner loop goes till N, the big O will be O(M*N) as long as there is no other tricky code. So in this case, you multiply n by 4.

Then the rule of constant multiplication applies. 4 is a constant, so O(n*4) simplifies to O(n).

OTHER TIPS

Yes, that's O(4*n), which is the same as O(n). You can think about it like this: since the loop repeats a fixed number of times, you can "unroll" it, like this:

for(var i = 1; i <= someNumber; i++) {
    // some arbitrary logic
    // Do something
    // Do something
    // Do something
    // Do something
}

This is definitely O(n).

The algorithm does run in time O(n), but your analysis is wrong. If you take those nested loops, you will realize that

  • The inner loop always runs a fixed number of times, so each time you execute the inner loop it does O(1) work.

  • The outer loop executes O(n) times. Each iteration does some constant amount of work, plus the work required to run the inner loop. Therefore, each iteration does O(1) work. Consequently, the total work required to run the loop nest is O(n).

Note that you don't add the two together - it's not correct to say that since the inner loop runs 4 times and the outer loop runs O(n) times, that the work is O(n) + 4 = O(n). Rather, you have to multiply them. It comes out to be the same answer, but that doesn't mean that the approach is correct. For example, if the inner loop also ran n times, then your analysis would incorrectly state that the runtime is O(n) + O(n) = O(n), when in reality the runtime would be O(n) × O(n) = O(n2).

Hope this helps!

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top