A
AiTechWorlds
AiTechWorlds
Big O complexity analysis measures how an algorithm's time or memory cost scales as input size grows, expressed as an upper bound like O(n) or O(log n) rather than an exact number of operations.
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