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

Big O Notation

Describing growth.

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

Big O is a short way to describe how an algorithm's steps grow. It sounds scary, but it's just a label. O of N means the steps grow in step with N, the size of the input. You'll see it everywhere, in docs, in interviews, and in code reviews.

Big O Notation
From the video: Big O Notation
  • A short label for growth
  • O(n): grows with n
  • You'll see it everywhere

The main Big O labels

Here are the labels you'll meet most, from fastest to slowest. O of one is constant, the same no matter how big the input. O of log N grows very slowly. O of N grows in step with the input. O of N log N is how good sorting grows. And O of N squared gets slow very quickly.

Big ONameExample
O(1)constantlook up a dict key
O(log n)logarithmicbinary search
O(n)linearloop over a list
O(n log n)linearithmicgood sorting
O(n²)quadraticnested loops

Feeling the difference

This code prints how many steps each label means, for a few input sizes. Log two counts how many times you can halve a number. Run it. Look at the last row. For a million items, O of log N is about twenty steps. O of N squared is a million million.

growth.pypython
import math
print(f"{'n':>9} {'log n':>6} {'n log n':>12} {'n squared':>16}")
for n in [10, 1_000, 1_000_000]:
    print(f"{n:>9,} {math.log2(n):>6.0f} {n * math.log2(n):>12,.0f} {n * n:>16,}")
Output
        n  log n      n log n        n squared
       10      3           33              100
    1,000     10        9,966        1,000,000
1,000,000     20   19,931,569 1,000,000,000,000

Summary

Big O labels how steps grow. O of one, log N, N, N log N, and N squared. Next, the two simple rules for working out Big O yourself.

Key takeaways
  • O(1) < O(log n) < O(n)
  • O(n log n) < O(n²)
  • It describes growth
Next up: Big O Rules — drop constants, keep the biggest