CODEWITHSUNDEEP
for-loopbig-o
Malaikatu Kargbo
Malaikatu Kargbo

Reputation: 313

How to calculate Big O of nested for loop

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

Upvotes: 5

Views: 5537

Answers (3)

jambrothers
jambrothers

Reputation: 1590

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).

Upvotes: 5

E.D.
E.D.

Reputation: 667

You misunderstand what O(n) means. It's hard to understand at first, so no shame in not understanding it.
O(n) means "This grows at most as fast as n". It has a rigorous mathematical definition, but it basically boils down to is this.
If f and g are both functions, f=O(g) means that you could pick some constant number C, and on big inputs like n, f(n) < C*g(n)." Big O represents an upper bound, and it doesn't care about constant factors, so if f=O(5n), then f=O(n).

Upvotes: 0

Ajax1234
Ajax1234

Reputation: 71471

You are correct about O(n^3) for your second example. You can calculate big O like this:

Any number of nested loops will add an additional power of 1 to n. So, if we have three nested loops, the big O would be O(n^3). For any number of loops, the big O is O(n^(number of loops)). One loop is just O(n). Any monomial of n, such as O(5n), is just O(n).

Upvotes: 0

Related Questions