Big O Basics

Big O tells you how time grows when your data grows.

You do not need heavy math here.
You only need this simple idea:

✅ If data becomes 10x larger, how much slower does your code get?

Common Big O types (in human words)

• O(1): constant time, stays fast
• O(log n): grows slowly
• O(n): grows linearly
• O(n log n): common in sorting
• O(n²): becomes slow quickly

Example: O(n) vs O(1)

O(n): search in a list

names = ["Tom", "Sarah", "Mike", "Ahsan"]

# worst case: it checks many items
print("Ahsan" in names)

O(1) average: search in a set

names = {"Tom", "Sarah", "Mike", "Ahsan"}
print("Ahsan" in names)

Why sets are faster for membership

A list checks one by one.
A set uses hashing to jump to the right place (average case).

Visual intuition

flowchart LR
  A[List membership] --> B[Check item1]
  B --> C[Check item2]
  C --> D[Check item3...]
  E[Set membership] --> F[Hash -> direct bucket]

Practical cheat sheet (Python built-ins)

• list append: usually fast
• list membership: slow for large lists
• dict get: fast average
• set membership: fast average
• sorting: n log n

Remember

• Big O helps you pick the right structure
• You don’t need math, focus on growth behavior
• Use set/dict for fast lookups