Introduction
Big O notation describes algorithm efficiency. Understanding it helps you write faster code and choose the right approach. This guide covers Big O fundamentals with examples.
What Is Big O
Definition
Big O describes how runtime scales with input size:
O(n) = "order n"
O(n²) = "order n squared"
Why It Matters
- Predict performance
- Compare algorithms
- Optimize code
- Pass interviews
Common Complexities
O(1) - Constant
# Always one operation
def first_element(arr):
return arr[0]
O(log n) - Logarithmic
# Binary search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
O(n) - Linear
# Single loop
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
O(n log n) - Linearithmic
# Sorting: merge sort, heap sort
# Most efficient comparison sorts
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
O(n²) - Quadratic
# Nested loops
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
O(2^n) - Exponential
# Recursive without memoization
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
O(n!) - Factorial
# Permutations
def permutations(arr):
if len(arr) <= 1:
return [arr]
result = []
for i, element in enumerate(arr):
remaining = arr[:i] + arr[i+1:]
for p in permutations(remaining):
result.append([element] + p)
return result
Visual Comparison
| Complexity | 10 | 100 | 1000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 |
| O(n) | 10 | 100 | 1000 |
| O(n log n) | 30 | 700 | 10,000 |
| O(n²) | 100 | 10,000 | 1,000,000 |
| O(2^n) | 1024 | 2^100 | 2^1000 |
Space Complexity
O(1) - Constant
def sum_arr(arr):
total = 0 # One variable
for num in arr:
total += num
return total
O(n) - Linear
def double_arr(arr):
return [x * 2 for x in arr] # New array
Analyzing Code
Rules
- Drop constants
- Drop lower terms
- Different inputs = different variables
Examples
# O(n) + O(n) = O(n)
def example1(n):
for i in range(n):
print(i)
for i in range(n):
print(i)
# O(n²) + O(n) = O(n²)
def example2(n):
for i in range(n):
for j in range(n):
print(i, j)
for i in range(n):
print(i)
# O(1) inside O(n) = O(n)
def example3(n):
for i in range(n):
x = i * 2 # O(1)
Common Patterns
Loops
- Single loop: O(n)
- Two nested loops: O(n²)
- Loop with halving: O(log n)
Recursion
- Single call: O(n)
- Binary tree recursion: O(2^n)
Data Structures
| Operation | Array | Linked List | Hash Table |
|---|---|---|---|
| Access | O(1) | O(n) | O(1) |
| Search | O(n) | O(n) | O(1) |
| Insert | O(n) | O(1) | O(1) |
| Delete | O(n) | O(1) | O(1) |
Practical Application
Choose Algorithms
| Input Size | Use |
|---|---|
| < 1000 | O(n²) okay |
| < 100K | O(n log n) |
| < 10M | O(n) |
| 10M+ | O(log n), O(1) |
Optimization
# Before: O(n²)
def has_duplicates_bad(arr):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
return True
return False
# After: O(n)
def has_duplicates_good(arr):
seen = set()
for num in arr:
if num in seen:
return True
seen.add(num)
return False
Conclusion
Big O helps you reason about efficiency. Focus on dominant factors, drop constants, and think about how algorithms scale. Practice analyzing code to build intuition.
Comments