How to calculate Big O of nested for loop

Question

Im under the impression that to find the big O of a nested for loop, one multuplies the big O of each forloop with the next for loop. Would the big O for:

    for i in range(n):
         for j in range(5):
              print(i*j)

be O(5n)? and if so would the big O for:

 for i in range(12345):
      for j in range(i**i**i)
           for y in range (j*i):
                print(i,j,y)

be O(12345*(i**i**i)*(j*i)? Or would it be O(n^3) because its nested 3 times? Im so confused

Answer 1

This is a bit simplified, but hopefully will get across the meaning of Big-O:

Big-O is about the question "how many times does my code do something?", answering it in algebra, and then asking "which term matters the most in the long run?"

For your first example - the number of times the print statement is called is 5n times. n times in the outer loop times 5 times in the inner loop. What matters most in the long run? In the long run only n matters, as the value of 5 never changes! So the overall Big-O complexity is O(n).

For your second example - the number of times the print statement is called is very large, but constant. The outer loop runs 12345 times, the inner loop runs one time, then 16 times, then 7625597484987... all the way up to 12345^12345^12345. The innermost loop goes up in a similar fashion. What we notice is all of these are constants! The number of times the print statement is called doesn't actually vary at all. When an algorithm runs in constant time, we represent this as O(1). Conceptually this is similar to the example above - just as 5n / 5 == n, 12345 / 12345 == 1.

The two examples you have chosen only involve stripping out the constant factors (which we always do in Big-O, they never change!). Another example would be:

def more_terms(n):
  for i in range(n):
    for j in range(n):
      print(n)
      print(n)
  for k in range(n):
    print(n)
    print(n)
    print(n)

For this example, the print statement is called 2n^2 + 3n times. For the first set of loops, n times for the outer loop, n times for the inner loop and then 2 times inside the inner lop. For the second set, n times for the loop and 3 times each iteration. First we strip out the constants, leaving n^2 + n, now what matters in the long run? When n is 1, neither really matter. But the bigger n gets, the bigger the difference is, n^2 grows much faster than n - so this function has complexity O(n^2).