
AI Computing
Algorithms: Big O Notation and Complexity Analysis
Why Algorithm Analysis Matters
Scalability: Will your code work with 1 million users? Performance: Can you process data faster? Resource Management: Optimize CPU and memory usage Technical Interviews: Core topic at Google, Amazon, Facebook
What is Big O Notation?
Big O describes how runtime/space grows as input size increases.
Notation: O(f(n)) where n = input size
Focus: Worst-case scenario (upper bound)
Common Time Complexities
O(1) - Constant Time
Performance: Same time regardless of input size
Examples:
- Array access by index
- Hash table lookup
- Push/pop on stack
codedef get_first(arr): return arr[0] # Always 1 operation # n=10 or n=1000000, same time!
O(log n) - Logarithmic Time
Performance: Halves search space each step
Examples:
- Binary search
- Balanced tree operations
codedef 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 # n=1000 → ~10 steps # n=1000000 → ~20 steps
Growth:
- n=10: 3-4 operations
- n=100: 6-7 operations
- n=1000: 10 operations
- n=1000000: 20 operations
O(n) - Linear Time
Performance: Grows directly with input
Examples:
- Linear search
- Array traversal
- Finding max/min
codedef linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1 # n=100 → up to 100 operations # n=1000 → up to 1000 operations
O(n log n) - Linearithmic Time
Performance: Slightly worse than linear
Examples:
- Merge sort
- Quick sort (average)
- Heap sort
codedef merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) # log n divisions right = merge_sort(arr[mid:]) return merge(left, right) # n operations per level # n=1000 → ~10,000 operations
Why faster than O(n²)?
- n=1000: O(n²)=1,000,000 vs O(n log n)=10,000
- 100x faster!
O(n²) - Quadratic Time
Performance: Nested loops over input
Examples:
- Bubble sort
- Selection sort
- Insertion sort
- Nested array comparisons
codedef bubble_sort(arr): n = len(arr) for i in range(n): # Outer loop: n for j in range(n-i-1): # Inner loop: n if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # n=100 → 10,000 operations # n=1000 → 1,000,000 operations!
Warning: Avoid for large datasets!
O(2ⁿ) - Exponential Time
Performance: Doubles with each input increase
Examples:
- Recursive fibonacci (naive)
- Tower of Hanoi
- Subset generation
codedef fibonacci(n): if n <= 1: return n return fibonacci(n-1) + fibonacci(n-2) # n=10 → 1,024 calls # n=20 → 1,048,576 calls! # n=30 → Over 1 billion calls!
Solution: Use memoization!
O(n!) - Factorial Time
Performance: Extremely slow
Examples:
- Traveling salesman (brute force)
- Permutations
code# n=10 → 3,628,800 operations # n=15 → Over 1 trillion operations!
Complexity Comparison Chart
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | |---|------|----------|------|------------|-------|-------| | 10 | 1 | 3 | 10 | 33 | 100 | 1,024 | | 100 | 1 | 7 | 100 | 700 | 10,000 | 1.3×10³⁰ | | 1000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 | ∞ |
Space Complexity
Memory usage as input grows
O(1) Space:
codedef sum_array(arr): total = 0 # Single variable for num in arr: total += num return total
O(n) Space:
codedef create_copy(arr): return arr.copy() # New array of size n
Rules for Calculating Big O
1. Drop Constants
O(2n) → O(n) O(500) → O(1) O(n/2) → O(n)
2. Drop Non-Dominant Terms
O(n² + n) → O(n²) O(n + log n) → O(n) O(n³ + n² + n) → O(n³)
3. Different Inputs = Different Variables
codedef compare_arrays(arr1, arr2): for a in arr1: # O(a) for b in arr2: # O(b) if a == b: return True return False # Time: O(a × b), NOT O(n²)
4. Add for Sequential Steps
codedef process(arr): # Step 1 for x in arr: # O(n) print(x) # Step 2 for x in arr: # O(n) print(x * 2) # Total: O(n) + O(n) = O(2n) = O(n)
5. Multiply for Nested Steps
codedef nested(arr): for x in arr: # O(n) for y in arr: # O(n) print(x, y) # Total: O(n × n) = O(n²)
Practice Examples
Example 1:
codedef find_pairs(arr): for i in range(len(arr)): # O(n) for j in range(i+1, len(arr)): # O(n) print(arr[i], arr[j]) # Answer: O(n²) - nested loops
Example 2:
codedef process_data(arr): arr.sort() # O(n log n) for x in arr: # O(n) print(x) return arr[0] # O(1) # Answer: O(n log n) - dominant term
Example 3:
codedef search_matrix(matrix, target): for row in matrix: # O(rows) if target in row: # O(cols) return True return False # Answer: O(rows × cols)
Optimization Strategies
1. Use Hash Tables
O(n²) → O(n)
code# Bad: O(n²) def has_duplicate_slow(arr): for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] == arr[j]: return True return False # Good: O(n) def has_duplicate_fast(arr): seen = set() for num in arr: if num in seen: return True seen.add(num) return False
2. Sort First
O(n²) → O(n log n)
3. Binary Search
O(n) → O(log n)
4. Memoization
O(2ⁿ) → O(n)
code# Bad: O(2ⁿ) def fib_slow(n): if n <= 1: return n return fib_slow(n-1) + fib_slow(n-2) # Good: O(n) def fib_fast(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_fast(n-1, memo) + fib_fast(n-2, memo) return memo[n]
Real-World Impact
Facebook: O(n²) algorithm with 1 billion users
- Operations: 1,000,000,000,000,000,000
- Time: Years!
Google Search: O(n log n) with billions of pages
- Fast enough for real-time results
Interview Tips
- Always analyze your solution
- State assumptions about input size
- Discuss tradeoffs (time vs space)
- Optimize if asked
- Use examples to verify
Practice Problems
- Analyze time complexity of quick sort
- Two sum problem - optimize to O(n)
- Find if array contains duplicates
- Reverse a linked list - space complexity
- Count inversions in array