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.

1def get_first(nums):
2  return nums[0]
3
4get_first([1, 2, 3, 4, 5, 6])

2. Logarithmic - O(log n)

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

1def binary_search(nums, target):
2    left, right = 0, len(nums) - 1
3    while left <= right:
4        mid = (left + right) // 2
5        if nums[mid] == target:
6            return mid
7        elif nums[mid] < target:
8            left = mid + 1
9        else:
10            right = mid - 1
11    return -1
12
13binary_search([1, 2, 3, 4, 5, 6], 4)

3. Linear - O(n)

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

1def print_items(nums):
2  for num in nums:
3    print(num)
4
5print_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.