In algorithms, we don't just care about getting the right answer; we care about how much it costs to get there.
Big O Notation: Predictive Power
Big O notation allows us to describe the upper bound of an algorithm's running time in terms of the input size $n$. It is the universal language of complexity.
- O(1): Constant (Instant)
- O(log n): Logarithmic (Binary Search)
- O(n): Linear (Simple Scan)
- O(n log n): Linearithmic (Efficient Sorting)
- O(n²): Quadratic (Nested Loops)
The Sorting Spectrum
Sorting is the cornerstone of algorithmic thinking. Most complex problems become trivial once the data is ordered.
Bubble Sort (The Intuitive Path)
- Time: O(n²)
- Logic: Compare adjacent elements and swap if they are in the wrong order. Repeat until stable.
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}Merge Sort (Divide & Conquer)
- Time: O(n log n)
- Logic: Split the array into halves, sort each half recursively, and merge them back together. Reliable and stable.
Quick Sort (The High-Speed Gamble)
- Time: O(n log n) average / O(n²) worst-case
- Logic: Pick a pivot, partition the array, and recursively sort the partitions. Extremely fast in practice.
"The difference between O(n) and O(n log n) is the difference between a project that succeeds and one that fails."