A
AiTechWorlds
AiTechWorlds
Picture two restaurants, each with 5 tables.
Restaurant A has one waiter who walks to every single table every minute to check if anyone needs something. With 5 tables, he checks 5 times per minute. Manageable.
Restaurant B has a buzzer system. Customers press a button and the waiter comes instantly — regardless of how many tables there are.
Now both restaurants expand to 500 tables.
Restaurant A's waiter is now walking 500 checks per minute — completely overwhelmed, customers waiting 10 minutes for attention.
Restaurant B? Still instant. Nothing changed.
This is the core insight of Big O analysis: how does performance scale as input grows? The answer determines whether your software works at 5 users or 5 million users.
Big O notation describes the upper bound of an algorithm's growth rate. It answers: as input size n grows toward infinity, how does the number of operations grow?
Formal definition: f(n) is O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.
In plain English: we care about the dominant term as n gets large. Constants and lower-order terms are dropped.
Why drop constants?
3n and 100n are both O(n) — they both scale linearly| Complexity | Name | n=10 | n=100 | n=1,000 | n=10,000 |
|---|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 | 1 |
| O(log n) | Logarithmic | 3 | 7 | 10 | 13 |
| O(n) | Linear | 10 | 100 | 1,000 | 10,000 |
| O(n log n) | Linearithmic | 33 | 664 | 9,966 | 132,877 |
| O(n²) | Quadratic | 100 | 10,000 | 1,000,000 | 100,000,000 |
| O(n³) | Cubic | 1,000 | 1,000,000 | 10⁹ | 10¹² |
| O(2ⁿ) | Exponential | 1,024 | 10³⁰ | 10³⁰¹ | ∞ (unusable) |
| O(n!) | Factorial | 3,628,800 | 10¹⁵⁷ | ∞ | ∞ (unusable) |
O(n!) and O(2ⁿ) become completely impractical even for moderate inputs.
Operations
|
| O(n²)
| ****
| ****
| O(n log n)
| ++++++
| O(n) ....
| ....
| O(log n) ---
| O(1) ___________________________________________
+-------------------------------------------------> n
The flatter the curve, the better the algorithm scales.
Rule 1: Statements execute in O(1)
x = 5 # O(1)
y = x + 1 # O(1)
print(y) # O(1)
# Total: O(1)
Rule 2: Loops multiply
for i in range(n): # runs n times
print(i) # O(1) each time
# Total: O(n)
Rule 3: Nested loops multiply
for i in range(n): # n times
for j in range(n): # n times each
print(i, j) # O(1) each
# Total: O(n × n) = O(n²)
Rule 4: Sequential blocks add, take the dominant
for i in range(n): # O(n)
print(i)
for i in range(n): # O(n)
for j in range(n):
print(i,j) # O(n²)
# Total: O(n) + O(n²) = O(n²) ← dominant term wins
# O(1) — no matter how big the array, one operation
def first_element(arr):
return arr[0]
# Input: [10, 20, 30, 40, 50]
# Output: 10 (always 1 step)
# O(log n) — problem halves each step
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # find middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # search right half
else:
hi = mid - 1 # search left half
return -1
# Input: arr=[1,3,5,7,9,11,13], target=7
# Step 1: mid=3, arr[3]=7 → FOUND at index 3
# Output: 3 (found in 1 step out of 7 elements)
# O(n) — one pass through data
def find_max(arr):
return max(arr)
# Input: [3, 1, 4, 1, 5, 9, 2, 6]
# Output: 9 (checks every element once)
# O(n log n) — Python's built-in sort (Timsort)
def sort_it(arr):
return sorted(arr)
# Input: [5, 2, 8, 1, 9, 3]
# Output: [1, 2, 3, 5, 8, 9]
# O(n²) — nested loops, count actual operations
def bubble_sort_count(arr):
ops = 0
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
ops += 1
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return ops
arr = list(range(100, 0, -1)) # worst case: reverse sorted
print(bubble_sort_count(arr))
# Output: 4950 (exactly n*(n-1)/2 = 100*99/2 comparisons)
We also measure how much extra memory an algorithm uses (beyond the input itself).
# O(1) space — uses a fixed number of variables
def sum_array(arr):
total = 0 # one variable, regardless of input size
for x in arr:
total += x
return total
# O(n) space — creates a new array of size n
def double_all(arr):
return [x * 2 for x in arr] # new list of n elements
# O(log n) space — recursion depth of binary search
def bin_search_recursive(arr, target, lo, hi):
if lo > hi: return -1
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target:
return bin_search_recursive(arr, target, mid+1, hi)
else:
return bin_search_recursive(arr, target, lo, mid-1)
# Stack depth is O(log n) — each call halves the range
Big O usually describes the worst case, but all three matter:
| Case | Meaning | Example (QuickSort) |
|---|---|---|
| Best case (Ω) | Most favorable input | Already sorted with ideal pivot → O(n log n) |
| Average case (Θ) | Expected over random inputs | Random data → O(n log n) |
| Worst case (O) | Most unfavorable input | Already sorted with last element as pivot → O(n²) |
Practical example — linear search:
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
# Best case: target is arr[0] → O(1) — found immediately
# Worst case: target not in arr → O(n) — checked everything
# Average: target is in middle → O(n/2) = O(n)
Big O is the language of technical interviews. You'll be expected to:
Python built-in complexities to memorize:
| Operation | Data Structure | Complexity |
|---|---|---|
arr[i] | List | O(1) |
arr.append(x) | List | O(1) amortized |
x in arr | List | O(n) |
x in dict | Dictionary | O(1) average |
dict[key] | Dictionary | O(1) average |
sorted(arr) | Any | O(n log n) |
Next lesson: Recursion — the foundation of many O(log n) and O(n log n) algorithms.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises