AI Hints
Home›DSA in Python Tutorial›Measuring Speed
DSA in Python · Lesson 6 of 132

Big O Rules

Drop constants, keep the biggest.

⏱ 2 min read▶ Video at 5:45🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Working out Big O is easier than it looks. There are just two rules. Drop the constants, and keep only the biggest term. Let's see why they make sense.

Big O Rules
From the video: Big O Rules
  • Two simple rules
  • Drop the constants
  • Keep the biggest term

Two loops in a row

This function loops over the list twice, once to find the smallest number, and once to find the biggest. That's two N steps. But Big O drops the two, because doubling doesn't change the shape of the growth. It's still O of N. Run it.

rules.pypython
def min_and_max(numbers):
    smallest = numbers[0]
    for n in numbers:
        smallest = min(smallest, n)
    largest = numbers[0]
    for n in numbers:
        largest = max(largest, n)
    return smallest, largest

print(min_and_max([5, 3, 9, 1, 7]))
Output
(1, 9)

Keep the biggest term

If code has a loop, and then a loop inside a loop, that's N plus N squared steps. When N is a million, N squared is so big that the plain N doesn't matter at all. So we keep only the biggest term. O of N squared.

2n→ O(n)
n + 100→ O(n)
n² + n→ O(n²)
5→ O(1)

Summary

Drop constants, and keep the biggest term. Two loops in a row is O of N. A loop inside a loop is O of N squared. Next, we'll see each one in real code.

Key takeaways
  • Drop constants
  • Keep the biggest term
  • 2n → O(n)
Next up: O(1) and O(n) — constant and linear