SB Big O Simplification and Practice

Section 15.3 Big O Simplification and Practice

One more important topic in Big O Analysis is simplification. We won’t get too deep into the math, but here are a few general rules:

Constant time operations always simplify to O(1). For instance, O(3) and O(1000000) both simplify to O(1).

Added constants are ignored when a larger factor is around. For instance, O(n + 1) is just O(n).

Multiplication by a constant factor simplifies to the factor, such as O(3n) becoming O(n).

Added polynomials are ignored when a larger factor is around. For instance, O(n! + n) is just O(n!), or O(n^2 + n) is just O(n^2).

With nested loops, any inner loop factors are multiplied by the outer loop factor.

Example 1: Find the time complexity of this program. Be careful of the nested loop.

def example_func(n):
    for i in range(n):
      for j in range(n):
        print(i * j)

O(1)
Incorrect; we have two nested loops here.
O(logn)
Not quite. You typically see O(logn) more often in search/sort algorithms.
O(n)
Incorrect; both loops (one of which is nested) depend on n.
O(n^2)
Correct! Both loops depend on n, and one loop is nested, which multiplies it by the parent factor.

Example 2: Find the time complexity of this program.

def example_func(n):
    for i in range(n):
      for j in range(10000):
        print(j)

O(1)
Not quite; we one loop going to n and one loop going to a constant time.
O(logn)
Not quite. You typically see O(logn) more often in search/sort algorithms.
O(n)
Correct! O(10000n) simplifies to O(n).
O(n^2)
Incorrect. We only have one loop going to n, the inner loop is going to a constant.

Example 3: Find the time complexity of this program. Apply the same rules that you do for a for loop.

n = input()
i = 0
while i < n:
  print(i)
  i += 1

You have attempted of activities on this page.