Learn
B2.4.1 | BIG O AND SCALABILITY
01 | WILL IT STILL WORK WELL WITH A MILLION ITEMS?
A program finds a student in a class list almost instantly. The same approach might struggle when searching millions of accounts. The important question is not only whether the program is correct, but how the work grows as the input grows.
Algorithm efficiency concerns resources used to solve a problem, commonly time and memory. Scalability concerns how well the approach handles increasing input size. Big O describes a growth bound rather than a stopwatch reading.
We will count operations in specific algorithms, simplify those counts and connect the resulting growth rates to larger inputs. The main focus is time complexity; space complexity is treated separately.
02 | FIRST DEFINE WHAT N MEANS
Before writing O(n), state what n measures. For a list search, n is the number of elements. For text processing, it may be the number of characters. For a graph, vertices and edges can be separate dimensions.
“The algorithm is O(n)” is incomplete if the reader cannot tell what grows. Searching 100 short integers and searching 100 enormous documents can involve different work inside each comparison.
Our introductory examples assume fixed-size values and constant-time elementary arithmetic, comparisons and indexed array/list access. If an operation processes a growing string or a very large integer, that assumption may need revision.
03 | COUNT WORK INSTEAD OF SECONDS
values = [4, 7, 2, 9]
total = 0
additions = 0
for value in values:
total = total + value
additions = additions + 1
print(total, additions)
This outputs 22 and 4. We selected adding a value to total as the operation to count. For n values, that addition happens n times. The counter is instrumentation for learning, not an extra part required by the original total algorithm.
A more detailed model could count assignments, checks and updates too, giving a formula such as an + b for fixed constants a and b. Both models still have linear growth.
Actual elapsed time also depends on hardware, implementation, language and input characteristics. Operation counts help compare growth without pretending those factors disappear.
04 | WHAT BIG O ACTUALLY SAYS
T(n) is O(f(n)) means that, beyond some input size, T(n) is no larger than a fixed positive constant times f(n). It is an asymptotic upper bound: it describes growth for sufficiently large inputs.
In classroom algorithm classification, we normally report the most informative standard bound for the stated case, rather than a deliberately loose one. A linear count n is technically also O(n²), but O(n) communicates its growth more precisely.
Big O does not itself mean worst case. We must specify whether the function being bounded describes best-case, average-case or worst-case work. In our examples, assume worst-case time unless another case is explicitly stated.
Theta, written Θ, describes a tight asymptotic bound. We use Big O throughout this lesson while explaining the actual operation counts behind the usual classifications.
05 | O(1): CONSTANT WORK
values = [4, 7, 2, 9]
first = values[0]
print(first)
With a nonempty indexed list under our model, retrieving one element uses a bounded amount of work regardless of how many elements the list contains. This is O(1), called constant time.
O(1) does not mean exactly one instruction or one second. A fixed block of twenty elementary operations is still constant time.
The example assumes values already exists. Creating or reading the whole list as part of the measured task would add work that grows with n. Define the boundary of the algorithm being analysed.
06 | O(N): ONE FULL PASS
def total_values(values):
total = 0
for value in values:
total = total + value
return total
print(total_values([4, 7, 2, 9]))
The body performs constant work for each of n values, so the total work grows proportionally to n: O(n), or linear time. Doubling n roughly doubles the growing part of the work.
Do not count the number of source-code lines. A four-line function can process a billion items, while a much longer fixed block can remain O(1).
07 | DROP CONSTANT FACTORS AND LOWER-ORDER TERMS
| Operation-count model | Dominant growth | Standard classification |
|---|---|---|
| 7 | Constant | O(1) |
| 3n + 10 | n | O(n) |
| 5n² + 2n + 8 | n² | O(n²) |
| 4 log₂ n + 6 | log n | O(log n) |
| 2n log₂ n + 9n | n log n | O(n log n) |
A fixed multiplier changes the scale, but not the growth class. A lower-order term eventually contributes less than the dominant term as n grows.
For 5n² + 2n + 8, keep n² for the standard classification. This simplification does not say the dropped work is zero, or that constants never matter for actual performance.
Only drop factors that are constant relative to the stated input size. If m also grows, nm cannot generally be simplified to n.
08 | SEQUENTIAL LOOPS: ADD THEIR WORK
def two_passes(values):
total = 0
for value in values:
total = total + value
matches = 0
for value in values:
if value > 5:
matches = matches + 1
return total, matches
print(two_passes([4, 7, 2, 9]))
The loops occur one after the other. Each visits n values, so the repeated work is n + n = 2n, giving O(n), not O(n²). The result is (22, 2).
Add the costs of sequential stages. If one stage is O(n) and a later stage is O(n²), the overall standard bound is O(n²), because the quadratic term dominates.
09 | NESTED LOOPS: COUNT HOW OFTEN THE INNER BODY RUNS
def count_pairs(values):
count = 0
for left in values:
for right in values:
count = count + 1
return count
print(count_pairs([4, 7, 2, 9]))
For each of n outer values, the inner loop visits n values. The increment runs n × n = n² times, so this algorithm is O(n²), called quadratic time. Four values produce 16 ordered pairs, including each item paired with itself.
Doubling n multiplies n² by four. This is why a nested comparison approach can become expensive quickly even when it feels fast for a tiny list.
10 | NESTING ALONE DOES NOT PROVE QUADRATIC TIME
def fixed_checks(values):
count = 0
for value in values:
for check in range(3):
count = count + 1
return count
print(fixed_checks([4, 7, 2, 9]))
The inner loop runs a fixed three times, not n times. Its total body count is 3n, giving O(n). For four values, the result is 12.
A loop nested three levels deep is not automatically O(n³). Inspect the actual bounds and the work inside. Nesting tells you where to investigate; it does not replace calculation.
11 | TRIANGULAR LOOPS: CHANGING INNER BOUNDS
def count_unique_pairs(values):
count = 0
for i in range(len(values)):
for j in range(i + 1, len(values)):
count = count + 1
return count
print(count_unique_pairs([4, 7, 2, 9]))
The inner counts are n − 1, n − 2, …, 1, 0. Their sum is n(n − 1)/2 = (n² − n)/2, so the standard bound is still O(n²). For four values, 3 + 2 + 1 = 6 pairs.
This avoids self-pairs and duplicate reversed pairs, reducing the constant amount of work compared with the full grid. It does not change the quadratic growth class.
12 | TWO INPUT SIZES: O(NM)
Suppose one list contains n students and another contains m clubs, and the algorithm checks every student-club pairing. The work is n × m, giving O(nm).
Do not automatically write O(n²) unless the relationship between the input sizes justifies it. If m is fixed at 3, the work is O(n); if m grows proportionally to n, quadratic growth describes that situation.
A helpful analysis names every independently growing dimension. This prevents a hidden assumption about one collection being the same size as another.
13 | LOGARITHMS: COUNT HOW MANY HALVINGS
Start with 16 candidates. Repeatedly halve the remaining candidates: 16 becomes 8, then 4, then 2, then 1. It takes four halvings. Since 2⁴ = 16, log₂ 16 = 4.
A logarithm answers a question about powers. log₂ n asks what power of 2 gives n. When a search repeatedly removes about half the remaining possibilities, the number of stages grows logarithmically.
Increasing n from 1,024 to 1,048,576 multiplies the candidates by 1,024, but raises log₂ n only from 10 to 20. Different fixed logarithm bases differ by a constant factor, so the standard class is O(log n).
14 | A HALVING LOOP YOU CAN COUNT EXACTLY
def halving_steps(n):
steps = 0
while n > 1:
n = n // 2
steps = steps + 1
return steps
print(halving_steps(16))
print(halving_steps(20))
Both calls return 4: 20 becomes 10, 5, 2, 1. For positive integer n, the number of body executions is floor(log₂ n). The loop has O(log n) growth for large n.
The division is integer division, and this loop stops at 1. Other halving algorithms can have different rounding and final checks, so log₂ n is not automatically their exact operation count.
The inverse pattern, doubling a counter from 1 until it reaches n, is also logarithmic when each iteration does constant work.
15 | LINEAR SEARCH: STATE THE CASE
def linear_search(values, target):
for index in range(len(values)):
if values[index] == target:
return index
return -1
print(linear_search([2, 4, 6, 8], 8))
The output is 3, the zero-based index of 8. In the worst case, the target is last or absent, requiring n equality checks: O(n). In the best case, the first item matches, requiring one check: O(1).
Under the specific assumption that the target is present and equally likely at every position, the average number of equality checks is (n + 1)/2, which is O(n). Different input distributions require different average-case reasoning.
An early return does not make every case constant time. It improves some inputs while leaving a full scan possible.
16 | BINARY SEARCH: DISCARD HALF THE CANDIDATES
def binary_search(values, target):
low = 0
high = len(values) - 1
probes = 0
while low <= high:
middle = (low + high) // 2
probes = probes + 1
if values[middle] == target:
return middle, probes
elif values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1, probes
print(binary_search([2, 4, 6, 8, 10, 12, 14, 16], 16))
This returns (7, 4): index 7 found after four midpoint probes. A probe is one loop iteration inspecting a midpoint; a probe can involve more than one primitive comparison. Do not label four probes as exactly four relational operations.
The data must already be sorted, and this implementation assumes constant-time indexed access. Each unsuccessful probe discards about half the remaining candidate interval, giving worst-case O(log n) time and best-case O(1).
For this implementation and n ≥ 1, at most floor(log₂ n) + 1 probes are needed. This differs from the previous halving loop’s count because the stopping and checking rules differ.
If unsorted data must first be sorted for one search, include that preparation cost. An O(log n) search alone does not establish an O(log n) whole task.
17 | O(N LOG N): REPEATED LINEAR WORK ACROSS LEVELS
Merge sort divides a list into smaller pieces, sorts them and merges sorted pieces. In the standard analysis, there are about log₂ n levels of division, and the total merging work across each level is O(n).
Linear work across logarithmically many levels gives O(n log n) overall time. For powers of two, n log₂ n is a useful growth model; it is not a universal exact count of merge-sort comparisons.
A loop that runs n times and performs an O(log n) helper on each iteration also has O(n log n) work under those assumptions. Count work inside called functions, not only the visible loop header.
18 | BUBBLE SORT: A PARTICULAR VERSION MATTERS
def bubble_sort(values):
items = values.copy()
comparisons = 0
for end in range(len(items) - 1, 0, -1):
for i in range(end):
comparisons = comparisons + 1
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i]
return items, comparisons
print(bubble_sort([4, 1, 3, 2]))
This version makes (n − 1) + … + 1 = n(n − 1)/2 adjacent comparisons, whether the list starts sorted or reversed. It returns ([1, 2, 3, 4], 6), and its comparison time is O(n²) even in the best case for this implementation.
An optimized version with a swapped flag can stop after a pass with no swaps, giving O(n) best-case time on an already sorted list while retaining O(n²) worst-case time. State which algorithm version and which case you mean.
The copy costs O(n) additional space here. Calling the entire shown function in-place would be inaccurate, even though its swap stage uses only constant temporary space.
19 | EXPONENTIAL AND FACTORIAL GROWTH
An exhaustive subset search may examine 2ⁿ subsets because each of n items can be included or excluded. Enumerating every ordering of n distinct items produces n! permutations. These are explosive growth models.
Doubling n does not merely double 2ⁿ. Moving from n to n + 1 doubles 2ⁿ; moving from n to 2n squares it. For factorials, adding one item multiplies n! by n + 1.
The time to generate, copy or evaluate each candidate may add work beyond the candidate count. For example, explicitly writing all length-n permutations costs at least proportional to n × n! output items. Do not silently equate candidate count with the full implementation cost.
20 | COMPARE GROWTH AT THE SAME INPUT SIZE
| n | log₂ n | n | n log₂ n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 8 | 3 | 8 | 24 | 64 | 256 |
| 16 | 4 | 16 | 64 | 256 | 65,536 |
| 32 | 5 | 32 | 160 | 1,024 | 4,294,967,296 |
These are growth-model values, not measured runtimes. The constants and operations differ between real algorithms. The table shows why growth class becomes important as input sizes increase.
For the usual positive growing inputs, common classes increase from constant to logarithmic, linear, linearithmic, quadratic, cubic, exponential and factorial. Small-input crossovers can differ because constant factors matter.
21 | INTERACTIVE: SCALE THE INPUT
Choose an input size and compare mathematical growth models. The chart uses a logarithmic vertical scale so large values remain visible: equal vertical distances represent equal multiplicative changes. The exact table is the clearest way to compare the numbers. These are model counts, not seconds.
Predict the change from 8 to 16 before checking. n doubles, n² becomes four times larger, and 2ⁿ rises from 256 to 65,536. A logarithmic chart compresses these differences visually; always read the values and axis description.
22 | ESTIMATE THE EFFECT OF DOUBLING
| Model | T(2n) / T(n) | Interpretation |
|---|---|---|
| 1 | 1 | About unchanged |
| log₂ n | 1 + 1/log₂ n | One extra halving level |
| n | 2 | Twice the growing work |
| n log₂ n | 2(1 + 1/log₂ n) | Slightly more than twice |
| n² | 4 | Four times |
| n³ | 8 | Eight times |
| 2ⁿ | 2ⁿ | A rapidly growing multiplier |
Suppose a genuinely quadratic dominant term takes 2 seconds at one sufficiently large size. Doubling the size suggests roughly 8 seconds under the same conditions. This is a model-based estimate, not a guaranteed timing.
Big O by itself is only a bound. Timing extrapolations also assume the named term describes the dominant observed work and that hardware, implementation and operating conditions stay comparable.
23 | HIDDEN WORK IN CONVENIENT OPERATIONS
A single line can hide an entire loop. sum(values) and making a full list copy both take O(n) time in the usual model. Searching for membership in an unsorted list can also inspect all n elements.
If a loop runs n times and performs a fresh full sum of the same n-element list inside each iteration, its time becomes O(n²). If that sum can be computed once beforehand without changing the requirements, the total may become O(n).
Creating a Python slice of k list elements copies k references, so it costs O(k) time and additional space. An index-based binary search avoids copying a shrinking list at each step.
Always include helper functions, data preparation and required output in the analysis boundary. A short expression is not necessarily a constant-time operation.
24 | TIME AND AUXILIARY SPACE ARE DIFFERENT
Time complexity measures growth of work. Auxiliary space complexity measures extra working memory beyond the input, under the stated convention. An algorithm can be linear in time and constant in auxiliary space.
Summing a list with one running total uses O(n) time and O(1) auxiliary space in our fixed-size-value model. Building a new list of n doubled values uses O(n) time and O(n) space for that result.
State whether output storage is included or reported separately. An iterative index-based binary search uses O(1) auxiliary space, while a recursive version normally keeps O(log n) call-stack frames.
A faster algorithm can use more memory. Efficiency comparisons should identify the resource and the constraints that matter.
25 | PUT THE ANALYSIS INTO A CLEAR ANSWER
Begin with the input size and case: “Let n be the number of items; consider the worst case.” Identify the counted operation and the number of executions. Simplify its growth, then explain the effect on scalability.
For the unique-pair loop: “The inner body runs (n − 1) + … + 1 = n(n − 1)/2 times. This is quadratic, O(n²). Doubling the input makes the dominant work approximately four times larger, so the method scales poorly for very large collections compared with a suitable linear approach.”
Use comparisons only when algorithms solve the same required problem under compatible assumptions. Binary search is not a drop-in replacement for unsorted linear search without addressing ordering and preparation.
26 | COMMON ERRORS AND A FINAL CHECK
| Mistake | Correction |
|---|---|
| Two sequential loops imply O(n²) | Add sequential costs: n + n gives O(n) |
| Every nested loop is quadratic | Inspect each bound; fixed inner work can give O(n) |
| O(1) means one second | It means bounded growth independent of input size |
| Big O always means worst case | State the case being bounded |
| Binary search is always exactly log₂ n comparisons | Count the implementation’s probes and comparisons carefully |
| Ignore a helper’s internal loop | Include the cost of each call |
| Smaller Big O guarantees faster for every n | Constants, inputs and implementation affect actual runtime |
Before completing an answer, check that n is defined, the resource and case are stated, the count matches the code, and the scalability conclusion follows from the growth model.