EasyVery High Frequency15 min
Time Complexity
How to measure and compare algorithm execution time as input grows.
Time complexity measures how the number of operations grows with input size n — ignore constants, keep the dominant term.
Time Complexity Analysis
Complexity Cheat Sheet
Operation
Time
Note
Single loop
O(n)
Two nested loops
O(n²)
Careful: sequential loops = O(n+m) not O(n×m)
Binary search
O(log n)
Halves search space each step
Sort (comparison)
O(n log n)
Lower bound for comparison sort
DFS/BFS on graph
O(V+E)
Visit each node and edge once
Memoized recursion
O(unique subproblems)
Each subproblem computed once
Subsets enumeration
O(2^n)
Each element in or out
Permutations
O(n!)
All orderings of n elements