[for Larry]
BigOGrowthCurves.mp4
- First, what problem does Big O solve?
- The short definition
- The mental model: count growth, not seconds
- Time complexity versus memory complexity
- Input space, auxiliary space, and total space
- Common time complexity classes
- Common memory complexity classes
- In-place algorithms
- Time-memory trade-offs
- Drop constants
- Keep the dominant term
- Time and memory cheat sheet
- References & Readings
When we compare algorithms, measuring the exact time in seconds is often misleading. The same programme may run faster or slower depending on the machine, compiler, language runtime, cache behaviour, and even what else the computer is doing at that moment [2].
Big O notation gives us a more stable question [1, 3].
Tip
As the input gets larger, how quickly does the cost grow?
That cost might be:
- the number of operations,
- the number of comparisons,
- the amount of memory used,
- the number of recursive calls,
- the number of temporary values created.
That is why Big O is useful. It does not tell us the precise running time or exact memory in bytes. It tells us the shape of growth [1, 2, 3].
Note
Big O is not about whether an algorithm is fast on one tiny example. It is about how the algorithm behaves as the input size tends to grow.
Big O notation describes an upper bound on the growth rate of a function. In algorithm analysis, that function usually represents the number of operations, memory cells, recursive calls, comparisons, or temporary data structures needed for an input of size n [1, 3, 6].
A more formal way to say this is:
f(n) = O(g(n))if, after some point,f(n)grows no faster than a constant multiple ofg(n)[1, 3].
For beginners, the useful translation is:
| Formal phrase | Practical meaning |
|---|---|
n |
The input size, e.g. number of items in a list |
f(n) |
The actual cost of the algorithm |
g(n) |
The simplified growth pattern we use to describe that cost |
| Constant multiple | We ignore fixed multipliers such as 2n, 10n, or 0.5n |
| After some point | We care mostly about large inputs |
So 3n + 20 becomes O(n), and 5n² + 100n + 9 becomes O(n²) [1, 3].
Important
Big O deliberately removes details such as constants and lower-order terms. This makes it easier to compare algorithms at scale.
Suppose n is the number of elements in a collection.
Input size n |
O(1) |
O(log n) |
O(n) |
O(n log n) |
O(n²) |
|---|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | ~33 | 100 |
| 100 | 1 | ~7 | 100 | ~664 | 10,000 |
| 1,000 | 1 | ~10 | 1,000 | ~9,966 | 1,000,000 |
| 1,000,000 | 1 | ~20 | 1,000,000 | ~19,931,569 | 1e12 |
These growth patterns are part of the wider language of computational complexity: we are not just asking can a problem be solved, but also how the required resources grow [2, 4].
Tip
Time complexity asks: how does the number of steps grow?
Memory complexity asks: how does the amount of memory grow?
So far, most examples have focused on time complexity.
Time complexity describes how the running work grows as the input gets larger.
Memory complexity, also called space complexity, describes how the memory needed by an algorithm grows as the input gets larger [6].
| Type | Question it answers | Example |
|---|---|---|
| Time complexity | How many steps does the algorithm take? | “How many list items do we check?” |
| Memory complexity | How much memory does the algorithm need? | “How many extra values, lists, sets, or stack frames do we create?” |
For example, these two functions both look at every number, so they both have O(n) time complexity.
from typing import List
def print_numbers(numbers: List[int]) -> None:
for number in numbers:
print(number)This function uses very little extra memory. It does not build a new list; it only reads the existing list one item at a time.
Time complexity: O(n)
Memory complexity: O(1) auxiliary space
Now compare it with this version:
from typing import List
def copy_numbers(numbers: List[int]) -> List[int]:
copied_numbers: List[int] = []
for number in numbers:
copied_numbers.append(number)
return copied_numbersThis function also loops through the list once, so the time complexity is still O(n). But it creates a new list that grows with the input size.
Time complexity: O(n)
Memory complexity: O(n) auxiliary space
Important
Two algorithms can have the same time complexity but different memory complexity.
When talking about memory complexity, there are three useful phrases.
| Phrase | Meaning |
|---|---|
| Input space | The memory used to store the input itself |
| Auxiliary space | The extra memory the algorithm creates while running |
| Total space | Input space + auxiliary space |
This distinction matters because people often say “space complexity” when they really mean “auxiliary space” [6, 7].
Suppose we are given this list:
numbers: list[int] = [4, 8, 15, 16, 23, 42]The list already exists before our algorithm runs. That is the input space.
If our algorithm creates another list, set, dictionary, or many recursive calls, that extra memory is auxiliary space.
Tip
In beginner algorithm analysis, when someone asks for “memory complexity”, they often mean:
How much extra memory does this algorithm use, not counting the input we were already given?
Example:
from typing import List
def get_first_number(numbers: List[int]) -> int:
return numbers[0]This uses the existing list and returns one value.
Input space: O(n)
Auxiliary space: O(1)
Total space: O(n)
The input list has n items, so the input space is O(n). But the function itself only uses constant extra memory.
Note
This is why you should be clear whether you are discussing total space or auxiliary space.
The work does not grow with the input size.
from typing import List
def is_last_element_odd(numbers: List[int]) -> bool:
return numbers[-1] % 2 != 0Even if the list has 10 elements or 10 million elements, this function checks only the last element.
Time complexity: O(1)
Memory complexity: O(1) auxiliary space
Tip
If there is no loop, no recursion, and no repeated work that depends on the list size, it is often a clue that we are looking at O(1) time.
Note
Best case: the list has one number, and we still only check the last element, so it is O(1).
Warning
Worst case: the list has one million numbers, and we still only check the last element, so it remains O(1).
The input, search space, or remaining work is reduced by a constant fraction at each step [1]. The most common beginner intuition is: how many times can I cut n in half until I reach 1?
from typing import List
def count_split_levels(numbers: List[int]) -> int:
size: int = len(numbers)
levels: int = 0
while size > 1:
size = size // 2
levels += 1
return levelsIf n = 8, the sizes go 8 → 4 → 2 → 1, so it takes 3 cuts. Since 2³ = 8, we say the number of cuts is log₂(8) = 3. If n = 16, the sizes go 16 → 8 → 4 → 2 → 1, so it takes 4 cuts, and 2⁴ = 16.
| Starting size | Halving steps | Why |
|---|---|---|
| 8 | 3 | 8 → 4 → 2 → 1 |
| 16 | 4 | 16 → 8 → 4 → 2 → 1 |
| 32 | 5 | 32 → 16 → 8 → 4 → 2 → 1 |
That is where the log n comes from: logarithm is the question “what power do I need?” Here, it is “how many halvings do I need?”
Time complexity: O(log n)
Memory complexity: O(1) auxiliary space
Tip
If each step removes half of what is left, think O(log n) before thinking O(n).
Note
Best case: the list has zero or one element, so the loop never runs and the function is O(1).
Warning
Worst case: the list is large, and the size is repeatedly halved until it reaches one, so the function is O(log n).
The work grows in direct proportion to the input size.
from typing import List
def contains_value(elements: List[str], value: str) -> bool:
for element in elements:
if element == value:
return True
return FalseIn the worst case, the function checks every element.
Time complexity: O(n)
Memory complexity: O(1) auxiliary space
Tip
A single pass over the list is usually a strong clue for O(n) time.
Note
Best case: the value is the first element, so the function returns after one check and this specific run is O(1).
Warning
Worst case: the value is missing or is the last element, so the function may check all n elements and is O(n).
O(n log n) often appears when an algorithm does logarithmic levels of work, and at each level it touches all n items in some way [1, 2].
A simplified example is repeatedly splitting a list into rounds, but doing one full pass over the current list per round.
from typing import List
def repeated_halving_with_full_pass(numbers: List[int]) -> int:
size: int = len(numbers)
total: int = 0
while size > 1:
for index in range(len(numbers)):
total += numbers[index]
size = size // 2
return totalHere is the idea:
| Part | Cost |
|---|---|
| One full pass over the list | O(n) |
| Number of times we halve the size | O(log n) |
| Total | O(n log n) |
So, the code above does a full pass, then halves the size, then does another full pass, then halves again, and so on. The full pass gives the n; the number of halving rounds gives the log n.
Time complexity: O(n log n)
Memory complexity: O(1) auxiliary space
Tip
If you see “do something to all items” combined with “repeat across halving rounds”, O(n log n) is a good first guess.
Note
Best case: if the list has zero or one element, the loop does not run, so that specific run is O(1).
Warning
Worst case: for a large list, each halving round does a full pass over the original list, giving O(n log n).
The work grows with the square of the input size. This commonly appears when an algorithm compares items repeatedly in nested passes [1].
Bubble sort is a nice example because we have already seen it.
from typing import List
def bubble_sort(numbers: List[int]) -> List[int]:
sorted_numbers: List[int] = numbers.copy()
length: int = len(sorted_numbers)
for outer_index in range(length):
swapped: bool = False
for inner_index in range(0, length - outer_index - 1):
if sorted_numbers[inner_index] > sorted_numbers[inner_index + 1]:
sorted_numbers[inner_index], sorted_numbers[inner_index + 1] = (
sorted_numbers[inner_index + 1],
sorted_numbers[inner_index],
)
swapped = True
if not swapped:
break
return sorted_numbersFor a list of 10,000 elements, a quadratic approach can easily involve tens of millions of comparisons.
Time complexity: O(n²)
Memory complexity: O(n) auxiliary space
Why is the memory complexity O(n) here?
Because this line creates a copy of the input list:
sorted_numbers: List[int] = numbers.copy()The copy grows with the input. If the input has n numbers, the copied list also has n numbers.
Tip
Nested loops do not automatically mean O(n²), but they are often a strong clue. Always ask how many times each loop actually runs.
Note
Best case: the list is already sorted, so the optimised bubble sort notices no swap happened and stops after one pass, giving O(n) time. However, this version still copies the list, so it uses O(n) auxiliary space.
Warning
Worst case: the list is reversed, so bubble sort keeps comparing and swapping through nested passes, giving O(n²) time and O(n) auxiliary space because of the copied list.
Memory complexity uses the same Big O notation, but it describes memory growth instead of running-time growth.
| Memory complexity | Meaning | Common beginner example |
|---|---|---|
O(1) |
Constant extra memory | A few variables, no new list |
O(log n) |
Logarithmic extra memory | A recursive algorithm that halves the problem each time |
O(n) |
Linear extra memory | Copying a list, building a set, storing results, or having up to n recursive calls on the call stack |
O(n²) |
Quadratic extra memory | Building a grid, matrix, or list of all pairs |
Important
Memory complexity is not about the exact number of bytes. It is about how memory grows as n grows.
Note
Recursion can use extra memory because unfinished function calls are kept on the call stack. For beginner analysis, the main question is usually: what is the deepest number of active recursive calls at one time?
This function adds up the numbers using only one extra variable: total.
from typing import List
def sum_numbers(numbers: List[int]) -> int:
total: int = 0
for number in numbers:
total += number
return totalEven if the input list gets bigger, the function still only needs a small fixed number of extra variables.
Time complexity: O(n)
Memory complexity: O(1) auxiliary space
Tip
A few variables such as index, total, maximum, or found usually count as O(1) auxiliary space.
This function creates a new list containing the doubled values.
from typing import List
def double_numbers(numbers: List[int]) -> List[int]:
doubled_numbers: List[int] = []
for number in numbers:
doubled_numbers.append(number * 2)
return doubled_numbersIf the input has 10 values, the new list has 10 values. If the input has 1,000 values, the new list has 1,000 values.
Time complexity: O(n)
Memory complexity: O(n) auxiliary space
Note
Creating a new list that grows with the input is one of the clearest signs of O(n) memory.
Sets are often used to remember what we have already seen.
from typing import List
def has_duplicate(numbers: List[int]) -> bool:
seen_numbers: set[int] = set()
for number in numbers:
if number in seen_numbers:
return True
seen_numbers.add(number)
return FalseThis is usually faster than comparing every number with every other number. But it uses extra memory.
Time complexity: O(n) average case
Memory complexity: O(n) auxiliary space
Why?
In the worst case, there are no duplicates, so the set may store all n numbers.
Tip
A dictionary or set can reduce time complexity, but it often increases memory complexity.
This function builds every possible pair from a list.
from typing import List, Tuple
def build_pairs(numbers: List[int]) -> List[Tuple[int, int]]:
pairs: List[Tuple[int, int]] = []
for left in numbers:
for right in numbers:
pairs.append((left, right))
return pairsIf there are 3 numbers, there are 9 pairs. If there are 1,000 numbers, there are 1,000,000 pairs.
Time complexity: O(n²)
Memory complexity: O(n²) auxiliary space
The nested loops explain the time complexity. The growing pairs list explains the memory complexity.
Warning
Nested loops can affect time. A growing nested data structure can affect memory.
An in-place algorithm modifies the existing data structure rather than creating a full new copy.
Here is an in-place version of bubble sort:
from typing import List
def bubble_sort_in_place(numbers: List[int]) -> None:
length: int = len(numbers)
for outer_index in range(length):
swapped: bool = False
for inner_index in range(0, length - outer_index - 1):
if numbers[inner_index] > numbers[inner_index + 1]:
numbers[inner_index], numbers[inner_index + 1] = (
numbers[inner_index + 1],
numbers[inner_index],
)
swapped = True
if not swapped:
breakThis version does not return a new list. It rearranges the original list.
Time complexity: O(n²) worst case
Memory complexity: O(1) auxiliary space
Compare that with the earlier version:
sorted_numbers: List[int] = numbers.copy()The copied version uses O(n) auxiliary space because it creates another list.
Important
“In-place” usually means the algorithm uses constant extra memory, such as O(1) auxiliary space. It does not mean the input takes no memory. The input still exists.
Sometimes we can use more memory to make an algorithm faster.
Here is a slow duplicate checker:
from typing import List
def has_duplicate_slow(numbers: List[int]) -> bool:
length: int = len(numbers)
for left_index in range(length):
for right_index in range(left_index + 1, length):
if numbers[left_index] == numbers[right_index]:
return True
return FalseThis compares each number with later numbers.
Time complexity: O(n²)
Memory complexity: O(1) auxiliary space
Now compare it with the set version:
from typing import List
def has_duplicate_fast(numbers: List[int]) -> bool:
seen_numbers: set[int] = set()
for number in numbers:
if number in seen_numbers:
return True
seen_numbers.add(number)
return FalseTime complexity: O(n) average case
Memory complexity: O(n) auxiliary space
The faster version uses extra memory to remember what it has already seen.
| Version | Time complexity | Memory complexity | Main idea |
|---|---|---|---|
| Nested-loop duplicate check | O(n²) |
O(1) |
Saves memory, but does more comparisons |
| Set-based duplicate check | O(n) average |
O(n) |
Uses memory to avoid repeated comparisons |
Important
Faster code sometimes uses more memory. Lower-memory code sometimes takes more time. This is called a time-memory trade-off.
from typing import List
def print_twice(numbers: List[int]) -> None: # function definition: O(1)
for number in numbers: # first loop over n items: O(n)
print(number) # one print per item: O(1), repeated n times
for number in numbers: # second loop over n items: O(n)
print(number) # one print per item: O(1), repeated n timesThis does 2n work, but we write it as O(n) [1, 3].
Time complexity: O(n)
Memory complexity: O(1) auxiliary space
The same rule applies to memory.
from typing import List
def make_two_copies(numbers: List[int]) -> tuple[List[int], List[int]]:
first_copy: List[int] = numbers.copy()
second_copy: List[int] = numbers.copy()
return first_copy, second_copyThis creates two new lists of size n.
Memory used: O(2n)
Simplified memory: O(n)
We drop the constant 2, so the auxiliary memory complexity is O(n).
Note
Best case: if the list is empty, nothing is printed, but the algorithmic pattern is still two linear passes.
Warning
Worst case: if the list has n items, the function prints n items twice, which simplifies from O(2n) to O(n).
Tip
What is the dominant term?
It is the part of the expression that grows the fastest as n gets larger. In O(1) + O(n) + O(n²), the O(n²) term dominates [1].
from typing import List
def mixed_work(numbers: List[int]) -> None: # function definition: O(1)
print(numbers[0]) # one access and one print: O(1)
for number in numbers: # first loop over n items: O(n)
print(number) # one print per item: O(1), repeated n times
for left in numbers: # outer loop over n items: O(n)
for right in numbers: # inner loop over n items for each outer item: O(n)
print(left + right) # one addition and one print: O(1), repeated n × n timesThe total work is approximately:
O(1) + O(n) + O(n²)
The dominant term is O(n²), so the whole function is O(n²).
Time complexity: O(n²)
Memory complexity: O(1) auxiliary space
This function prints many values, but it does not store all pairs in a list. So its auxiliary memory stays constant.
Now compare it with this version:
from typing import List, Tuple
def mixed_work_and_store_pairs(numbers: List[int]) -> List[Tuple[int, int]]:
pairs: List[Tuple[int, int]] = []
print(numbers[0])
for number in numbers:
print(number)
for left in numbers:
for right in numbers:
pairs.append((left, right))
return pairsThis version stores the pairs.
Time complexity: O(n²)
Memory complexity: O(n²) auxiliary space
Note
Best case: if the list is tiny, the function does little work, but the structure still contains the nested n × n part.
Warning
Worst case: as the list grows, the nested loop dominates the running time, and storing every pair dominates memory.
| Pattern | Time complexity | Memory complexity | Why |
|---|---|---|---|
| Access one list item | O(1) |
O(1) |
One operation, no growing structure |
| Loop through a list and print | O(n) |
O(1) |
Reads all items, stores almost nothing extra |
| Copy a list | O(n) |
O(n) |
Visits and stores n items |
| Build a new transformed list | O(n) |
O(n) |
Creates one output item per input item |
| Use a set to remember seen values | O(n) average |
O(n) |
Stores up to n seen values |
| Nested loop that only prints pairs | O(n²) |
O(1) |
Many operations, but no stored pair list |
| Nested loop that stores all pairs | O(n²) |
O(n²) |
Stores n × n pairs |
| Recursive countdown | O(n) |
O(n) |
One stack frame per active call |
| Recursive halving | O(log n) |
O(log n) |
One stack frame per halving level |
| In-place bubble sort | O(n²) worst case |
O(1) |
Rearranges the original list |
| Bubble sort on a copied list | O(n²) worst case |
O(n) |
Makes a full copy before sorting |
| Ref | Reading | Why it is useful |
|---|---|---|
| [1] | Wikipedia: Big O notation | Quick reference for the notation, formal definition, and examples. |
| [2] | Wikipedia: Time complexity | Useful background for best, worst, average, and resource-growth language. |
| [3] | Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News, 8(2), 18–24. https://doi.org/10.1145/1008328.1008329 | Classic paper clarifying asymptotic notation such as Big O, Big Omega, and Big Theta. |
| [4] | Hartmanis, J., & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117, 285–306. https://doi.org/10.2307/1994208 | Foundational paper for computational complexity as a formal area. |
| [5] | Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17, 449–467. https://doi.org/10.4153/CJM-1965-045-4 | Classic algorithm paper connected to the idea that efficient algorithms matter. |
| [6] | Wikipedia: Space complexity | Explains space complexity as memory required by an algorithm, including input space and auxiliary space. |
| [7] | GeeksforGeeks: Space Complexity | Beginner-friendly explanation of auxiliary space versus total space. |
| [8] | GeeksforGeeks: Auxiliary Space with Recursive Functions | Useful explanation that recursive call-stack space counts as auxiliary space. |
| [9] | Python Wiki: TimeComplexity | Useful Python-specific reference for common operation complexities. |