Introduction

The following are the most common cases of Big O a programmer should be aware of.

They're sorted from best to worse case.

1. Constant - O(1)

No matter how much data there is, it only takes one operation.

def get_first(nums):
return nums[0]

get_first([1, 2, 3, 4, 5, 6])

2. Logarithmic - O(log n)

Every step/action you take, you cut out half of the work.

def binary_search(nums, target):
  left, right = 0, len(nums) - 1
  while left <= right:
      mid = (left + right) // 2
      if nums[mid] == target:
          return mid
      elif nums[mid] < target:
          left = mid + 1
      else:
          right = mid - 1
  return -1

binary_search([1, 2, 3, 4, 5, 6], 4)

3. Linear - O(n)

Complexity grows in direct proportion to the size of the input/s.

def print_items(nums):
for num in nums:
  print(num)

print_items([1, 2, 3, 4, 5, 6])

4. Linearithmic - O(n log n)

Often is a nested iteration where within each operation done in linear time, there are actions being done in logarithmic time over the same size of data.

5. Quadratic - O(n²)

Nested loops over the same or similarly sized dataset.

6. Cubic — O(n³)

Triple nested loops over the same or similarly sized dataset. The number of operations grows with the cube of the input size.

7. Exponential — O(2ⁿ)

The number of operations doubles with each additional input. Often seen in recursive problems that branch into two or more calls per step.

8. Factorial — O(n!)

The number of operations doubles with each additional input. Often seen in recursive problems that branch into two or more calls per step.

Conclusion

Checkout this cheatsheet for more details.