Algorithms and Complexity
An algorithm is a precise set of steps to solve a problem. But not all algorithms are equal — some are dramatically faster than others on large inputs. Big O notation describes how an algorithm's performance scales.
Key Concepts
Big O Notation
O(1) is constant time — doesn't matter how big the input, it takes the same time (looking up an array element). O(n) is linear — double the input, double the time. O(n²) is quadratic — double the input, four times the time. Sorting 1 million items: O(n log n) vs O(n²) is the difference between seconds and hours.
Searching Algorithms
Linear search: check every element one by one — O(n). Binary search: on a sorted list, repeatedly halve the search space — O(log n). For 1 billion items, linear search averages 500 million comparisons; binary search needs at most 30.
Sorting Algorithms
Bubble sort (O(n²)): repeatedly compare adjacent elements and swap. Merge sort (O(n log n)): divide the list in half, sort each half, merge. Quick sort (O(n log n) average): pick a pivot, partition, recurse. Merge sort and quick sort power most real-world sorting.
🆕 Sorting Algorithm Visualizer
Watch Bubble Sort vs Merge Sort side-by-side. Count the comparisons!
✅ Check Your Understanding
1. What does O(n²) mean for an algorithm?
2. Why is binary search O(log n)?
3. Which sorting algorithm has O(n log n) time complexity?