Big-O Notation

The notation that tells you how an algorithm's running time grows as its input gets bigger.

Definition

Big-O notation is how you talk about a function's performance. It focuses on the most significant parts of the code that affect its execution time and memory. You will hear the term "time complexity," which just refers to how many times an algorithm interacts with data in the worst-case scenario. Space complexity is similar, but this time we are asking how much of the input we are storing ourselves.

Notations

These eight notations will cover nearly every algorithm you'll ever analyze. This table ranks them from fastest to slowest:

Complexity	Notation	Rank	Notes
Constant	O(1)	#1	The operation takes the same time whether the input has 10 elements or 10 million.
Logarithmic	O(log n)	#2	Each step cuts the input in half. A billion elements take about 30 steps.
Linear	O(n)	#3	Time grows in step with the input. Double the elements and the time doubles.
Linearithmic	O(n log n)	#4	The fastest general-purpose sorts land here, like merge sort and heapsort.
Quadratic	O(n^2)	#5	A loop nested inside another loop. Every element gets checked against every other element.
Cubic	O(n^3)	#6	Three nested loops. Fine at n = 100, hopeless past n = 10,000.
Exponential	O(2^n)	#7	Every new element doubles the running time. Even n = 50 is out of reach.
Factorial	O(n!)	#8	Grows faster than everything above it. Permutation problems live here.

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.

Analyzing Algorithms

To determine the complexity of an algorithm, follow these steps:

1. Identify

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.

2. Scaling

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?"

3. Significance

Focus on the most significant term and ignore less significant terms. In Big-O notation, the term that grows fastest as the input size increases is what we call the overall time complexity.

4. Worst-case Scenario

What is the worst possible input to your algorithm? Big-O notation usually describes the upper bound of an algorithm's running time, which is the longest time it could take to complete. This upper bound is basically a ceiling that says "no input can make the algorithm slower than that."

Amortized Time

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.

Start with a block that holds 1 value, and keep two counts running underneath it: appends made, and values copied by resizes.

Append 1 drops straight into the only slot. That's 1 append and 0 copies, and the block is already full.

Append 2 finds no room, so the block doubles to 2 and copies 1 value across before placing 2. The copies count moves for the first time.

Append 3 hits a full block again: double to 4, copy 2, place 3. Then append 4 slides into the last open slot without copying anything.

Append 5 forces the third resize: double to 8, copy 4. Appends 6, 7, and 8 fill the rest for free, so 8 appends have cost 7 copies total.

Append 9 is next and every slot is taken. Tap every value the resize has to copy.Nothing gets left behind in the old block.

All 8 move, so the copies count jumps from 7 to 15. But it took 8 appends to trigger that resize, and the next one is another 8 appends away.

Append 9 doubles the block to 16 and copies all 8 values, then appends 10 through 16 fill the open slots after it. Zoomed out, every block ends up as two halves: 8 copied on the left, 8 appended on the right.

Append 17 does it again: double to 32, copy 16, then 15 free appends fill the rest. By the time a block fills, the copies count is always 1 short of its size: 1 + 2 + 4 + 8 + 16 = 31 copies for 32 appends.

Fast forward to append 1,025: the block doubles to 2,048 and copies 1,024 values. Right after a resize is the worst moment to check the tally, and even here it reads 2,047 copies across 1,025 appends, about 2 per append.

Start with a block that holds 1 value, and keep two counts running underneath it: appends made, and values copied by resizes.

appends: 0
copies: 0
per append: 0.0

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).

Easy Example

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:

Identify: The loop iterates through the array and prints each element, so the operations to count are the for-loop and the print statement
Scaling: The loop runs once for each element in the array, so if the array has n elements, the loop executes n times. This means that the execution time scales linearly with the input size. If the input size were a billion, the loop would run a billion times
Significance: The most significant term is 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
Worst-case Scenario: The worst case is the same as the best case for this simple loop: the loop always runs 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).

Harder Example

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:

Identify: The basic operations in this example are the binary search loop, the calculation of total hours for a given speed, and the if-else statements that adjust the search range
Scaling: Binary search runs in 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 means 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)
Significance: The most significant term is the product of the binary search complexity (log m) and the iteration through the piles (n). Constant factors and less significant terms are ignored in Big-O notation
Worst-case Scenario: The worst case is when the binary search runs its maximum number of iterations and each iteration scans through all the piles. The time complexity in the worst case is 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).

Challenging Example

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:

Identify: The basic operations are the depth-first search (DFS) recursion and the iteration over the numbers in the list to build permutations
Scaling: The DFS function explores every possible permutation of the input list. For each position, it tries every number that hasn't been used yet, which leads to n! (factorial of n) permutations. The DFS function is called O(n!) times, and each call performs operations that take O(n) time
Significance: The most significant term is the product of the number of permutations (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!)
Worst-case Scenario: The worst case generates every permutation of the input list, which is also what happens on every run. The time complexity in the worst case is 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.

Best Practices

When you're choosing or writing an algorithm, these four habits keep it fast:

Most of your effort will be wasted if you misunderstand the problem, so get clear on what your input is and what your output has to be before you pick an algorithm. Then walk through the edge cases: an empty input, a single element, duplicates.

Big-O Notation

A mathematical notation to describe the performance and complexity of algorithms.

Big-O Notation

The notation that tells you how an algorithm's running time grows as its input gets bigger.

Definition

Notations

These eight notations will cover nearly every algorithm you'll ever analyze. This table ranks them from fastest to slowest:

Complexity	Notation	Rank	Notes
Constant	O(1)	#1	The operation takes the same time whether the input has 10 elements or 10 million.
Logarithmic	O(log n)	#2	Each step cuts the input in half. A billion elements take about 30 steps.
Linear	O(n)	#3	Time grows in step with the input. Double the elements and the time doubles.
Linearithmic	O(n log n)	#4	The fastest general-purpose sorts land here, like merge sort and heapsort.
Quadratic	O(n^2)	#5	A loop nested inside another loop. Every element gets checked against every other element.
Cubic	O(n^3)	#6	Three nested loops. Fine at n = 100, hopeless past n = 10,000.
Exponential	O(2^n)	#7	Every new element doubles the running time. Even n = 50 is out of reach.
Factorial	O(n!)	#8	Grows faster than everything above it. Permutation problems live here.