Beginner·2 min read
Complexity Analysis
Master Big-O, Omega, and Theta notations to analyze algorithm efficiency.
Complexity Analysis
Complexity analysis is the backbone of algorithm design. It tells us how efficient an algorithm is in terms of time and space.
Why Complexity Matters
Consider two approaches to find a number in an array of 1,000,000 elements:
- Linear Search: Check every element → up to 1,000,000 operations
- Binary Search: Halve the search space → at most 20 operations
That's a 50,000x difference.
Time Complexity
Time complexity measures how the number of operations grows with input size n.
| Header | |||
|---|---|---|---|
| Notation | Name | Meaning | Example |
| Header | |||
|---|---|---|---|
| O(1) | Constant | Same time regardless of n | Array index access |
| O(log n) | Logarithmic | Doubles input = 1 more step | Binary search |
| O(n) | Linear | Input doubles = time doubles | Linear search |
| O(n log n) | Linearithmic | Optimal comparison sort | Merge sort |
| O(n²) | Quadratic | Input doubles = 4x time | Bubble sort |
| O(2ⁿ) | Exponential | Each new input doubles time | Recursive Fibonacci |
Space Complexity
Space complexity measures additional memory used by an algorithm.
``python
O(1) space - only one extra variable
def find_max(arr):
maximum = arr[0]
for num in arr:
if num > maximum:
maximum = num
return maximum
O(n) space - creates a new array
def merge_sorted(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:])
result.extend(b[j:])
return result
``Asymptotic Notations
- Big-O (O): Upper bound — worst case
- Omega (Ω): Lower bound — best case
- Theta (Θ): Tight bound — average case
Master Rule of Thumb
- Drop constants: O(2n) → O(n)
- Drop lower-order terms: O(n² + n) → O(n²)
- Different inputs = different loop variables: O(a + b), not O(n)
Code Example
python
# Time complexity comparison
import time
def linear_search(arr, target):
for i, val in enumerate(arr): # O(n)
if val == target:
return i
return -1
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1 # O(log n)
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
# Demo
data = list(range(1_000_000))
target = 999_999
start = time.time()
linear_search(data, target)
print(f"Linear: {time.time()-start:.6f}s")
start = time.time()
binary_search(data, target)
print(f"Binary: {time.time()-start:.6f}s")Practice Problems
- 01Implement a function and count operations for O(1), O(n), O(n²) inputs
- 02Analyze the time and space complexity of a nested loop that prints pairs
- 03Write binary search and prove its O(log n) complexity