Big-O notation explained
What O(1), O(log n), O(n), O(n log n) and O(n^2) mean, with examples of each, for coding interviews and real code.
Big-O describes how an algorithm's work grows as the input grows, ignoring constant factors:
| Big-O | Name | Example |
|---|---|---|
| O(1) | constant | index into an array, hash lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scan a list once |
| O(n log n) | linearithmic | good sorting algorithms |
| O(n^2) | quadratic | nested loops over the same data |
For a million items, O(n^2) means about a trillion steps while O(n log n) is about 20 million. Picking the right data structure usually matters more than micro-optimizing code.
Example
#include <iostream>
#include <unordered_set>
#include <vector>
// O(n) with a hash set instead of O(n^2) with nested loops.
bool has_duplicate(const std::vector<int> &v) {
std::unordered_set<int> seen;
for (int x : v) {
if (!seen.insert(x).second) return true;
}
return false;
}
int main() {
std::cout << has_duplicate({3, 1, 4, 1, 5}) << " " << has_duplicate({2, 7, 1, 8}) << "\n";
return 0;
}
Output:
1 0