Big O notation describes an algorithm's performance or complexity, focusing on the most significant factors that affect its execution time or memory use.
Knowing the common notations is the foundation for analyzing and comparing the efficiency of algorithms. The table below covers the ones you'll see most often:
| 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 boundof an algorithm's running time, which is the longest time it could take to complete. That helps you understand the maximum resources the algorithm will need.
Amortized time analysis gives us an average running time per operation across many operations. Arrays start with a fixed size, but they sometimes need to be resized (typically doubled in size) when more space is required. Resizing involves copying every element to a new, larger array.
Resizing the array on its own is expensive, but amortized analysis shows that the average cost per operation stays low even when you include the resizings. Spreading those costs across many appends keeps the whole process efficient.
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 working with algorithms, keep these tips in mind to optimize their performance:
Define the problem clearly and identify the requirements before picking an algorithm. Break down the problem, think through the edge cases, and make sure you understand the input and output requirements first.
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