A function that feels instant on a hundred items can freeze on a million, and timing it won't warn you. A stopwatch only measures the input you tried, on the machine you tried it on. Big O notation is how you talk about speed in a way that survives both problems: it describes an algorithm's performance or complexity, focusing on the most significant factors that affect its execution time or memory use as the input grows.
Eight notations cover nearly every algorithm you'll ever analyze. The table below ranks them from fastest to slowest:
| Complexity | Notation | Rank |
|---|---|---|
| Constant | O(1) | #1 |
| Logarithmic | O(log n) | #2 |
| Linear | O(n) | #3 |
| Linearithmic | O(n log n) | #4 |
| Quadratic | O(n^2) | #5 |
| Cubic | O(n^3) | #6 |
| Exponential | O(2^n) | #7 |
| Factorial | O(n!) | #8 |
These notations let you predict how an algorithm's performance changes as the input grows. Once you can recognize these patterns, picking the right algorithm or data structure for a given problem gets a lot easier.
To determine the complexity of an algorithm, follow these steps:
Look for the basic operations that contribute to the algorithm's running time. These are the fundamental steps the algorithm takes: comparisons, assignments, arithmetic operations, and loops.
Figure out how the execution time scales with the input size. Look at how the number of basic operations changes as the input grows. A useful trick is to ask yourself: "What about an input size of a billion?"
Focus on the most significant term and ignore constant factors and less significant terms. In Big-O notation, the term that grows fastest as the input size increases is what dominates the overall time complexity.
Analyze the algorithm's performance in the worst case. Big-O notation usually describes the upper bound of an algorithm's running time, which is the longest time it could take to complete. That upper bound is a ceiling, no input can make the algorithm slower than that.
Amortized time is the average running time per operation once you spread the expensive operations across all the cheap ones. Arrays start with a fixed size, so when one fills up, the program allocates a bigger array (typically double the size) and copies every element over.
One resize on its own really is O(n). But watch what happens when you append 1,025 elements to an array that starts at capacity 1: it resizes at 1, 2, 4, all the way up to 1,024, which comes out to 2,047 copies total. Spread across 1,025 appends, that's about 2 copies per append, so appending stays O(1).
Let's start with a simple example. The code below shows a loop that iterates through an array of size n:
Let's apply the steps from earlier and walk through the code step by step:
n elements, the loop executes n times. Execution time scales linearly with the input size. If the input size were a billion, the loop would run a billion times.n, the number of iterations. Constant factors (like the time taken to print each element) are less significant and can be ignored in Big-O notation.n times. The time complexity in the worst case is O(n).Answer: The loop runs n times, so the time complexity is O(n).
This example uses binary search to find the minimum eating speed where all piles are eaten within a given number of hours:
To determine the time complexity of this algorithm, follow these steps:
O(log m) time, where m is the range of possible eating speeds (from 1 to the maximum pile size). Each iteration of the binary search calculates the total hours required, which involves iterating through all the piles in O(n) time, where n is the number of piles. The total time complexity is O(n log m).log m) and the iteration through the piles (n). Constant factors and less significant terms are ignored in Big-O notation.O(n log m).Answer: The binary search runs in O(log m) time, and for each iteration, it scans all piles in O(n) time. This results in a total time complexity of O(n log m).
This example generates all permutations of a list of numbers using depth-first search:
To determine the time complexity of this algorithm, follow these steps:
n! (factorial of n) permutations. The DFS function is called O(n!) times, and each call performs operations that take O(n) time.n!) and the operations within each DFS call (n). Constant factors and less significant terms are ignored in Big-O notation, so the time complexity is O(n * n!).O(n * n!).Answer: The DFS function runs in O(n * n!) time because it generates all possible permutations of the input list and performs operations for each permutation.
When you're choosing or writing an algorithm, these four habits keep it fast:
Most wasted effort comes from solving the wrong problem, so get clear on what goes in and what has to come out before you pick an algorithm. Then walk through the edge cases: an empty input, a single element, duplicates.
def print_elements(arr):
for i in range(len(arr)):
print(arr[i])def minEatingSpeed(self, piles: List[int], h: int) -> int:
left, right = 1, max(piles)
res = 0
while left <= right:
mid = (left + right) // 2
hours = 0
for pile in piles:
hours += math.ceil(pile / mid)
if hours > h:
left = mid + 1
else:
res = mid
right = mid - 1
return resdef permute(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
def dfs(index: int) -> None:
if not (index < len(nums)):
res.append(subset[:])
return
for num in nums:
if num not in subset:
subset.append(num)
dfs(index + 1)
subset.pop()
return
dfs(0)
return res