Published on

Big O Notation

Authors

O(1) - Constant

x = n[0] * n[0]

O(log n) - Logarithmic

for i in range(0, len(n), 3) # Reduces size of input data.
  print(n[i])

O(n) - Linear

for i in n:
  print(i)

O(n log n) - Quasilinear

r = []
for i in n:
  # Each step in the input data has log time complexity.
  r.append(binary_search(foo, i)

O(n^2) - Quadratic / Square

for i in n:
  for j in m: # Grows proportional.
    print(i, j)

O(2^n) - Exponential

def fibonacci(i): # Growth doubles with each addition to input.
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)