IB COMPUTER SCIENCE | B2.4.1 Big O and Scalability

Lesson objective

Describe algorithm efficiency by calculating operation counts and Big O bounds, stating assumptions and cases, and analysing scalability as input size grows.

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.

MATCH THE COMPLEXITY IDEA

Terminology

Terminology

Input size

The measure of data quantity that grows, often denoted n.

Time complexity

How an algorithm’s work grows with input size under a stated model.

Space complexity

How memory use grows with input size.

Auxiliary space

Extra working memory beyond the input, under a stated convention.

Scalability

How well an approach handles increasing input size.

Basic operation

An operation chosen as a useful unit of work to count.

Operation-count model

A formula describing counted work as input size changes.

Big O

An asymptotic upper bound on the growth of a stated cost function.

Asymptotic analysis

Analysis of growth for sufficiently large input sizes.

Constant factor

A fixed multiplier independent of the growing input size.

Dominant term

The term that determines eventual growth in a sum of standard cost terms.

Lower-order term

A term that grows more slowly than the dominant term.

Constant time O(1)

Work bounded independently of input size.

Logarithmic time O(log n)

Growth comparable to the number of repeated fixed-factor reductions.

Linear time O(n)

Work growing proportionally to input size in a tight linear model.

Linearithmic time O(n log n)

Growth combining a linear factor with a logarithmic factor.

Quadratic time O(n²)

Growth with the square of input size in the standard quadratic model.

Cubic time O(n³)

Growth with the cube of input size in the standard cubic model.

Exponential model 2ⁿ

A growth model doubling when n increases by one.

Factorial n!

The product of positive integers up to n, with 0! = 1.

Best case

The least work among permitted inputs of a given size.

Worst case

The greatest work among permitted inputs of a given size.

Average case

Expected work under a specified distribution of inputs.

Sequential stages

Stages performed one after another, whose costs are added.

Nested repetition

Repetition inside repetition; total work depends on both bounds.

Logarithm

An exponent needed to produce a value from a given base.

Binary search

Search of sorted indexed data by repeatedly reducing the candidate interval.

Probe

One inspection of a candidate, such as a midpoint in binary search.

Trade-off

A choice balancing resources or desirable properties.

Tight bound Θ

An asymptotic bound describing both upper and lower growth to constant factors.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which should be stated before analysing O(n)?
2. Which counts have a standard linear classification?
3. Which statements about Big O are correct?
4. Which full body counts are quadratic?
5. Which patterns can have logarithmic time under constant-work iterations?
6. Which are assumptions for the shown binary search analysis?
7. Which describe the shown unoptimized bubble sort?
8. When n doubles, which statements match the mathematical models?
9. Which statements about space are correct?
10. Which improve an efficiency explanation?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Calculate the standard Big O classification of 4n² + 12n + 7.

2. Explain why two consecutive full scans of the same n-item list are O(n).

3. Calculate how many inner-body executions occur when both nested loops run n times.

4. Calculate the growth class of a loop over n items with an inner loop of exactly 5 iterations.

5. Calculate the total pair checks for n = 6 in the triangular unique-pair loop, and state its general Big O.

6. Describe what log₂ 32 means in a halving analysis.

7. Compare worst-case linear search and binary search for sorted indexed data.

8. Explain why an early return does not make linear search O(1) in the worst case.

9. Calculate the expected multiplier in dominant quadratic work when input size triples.

10. Explain how a helper function can change the complexity of an outer loop.

11. Distinguish time complexity from auxiliary space complexity.

12. Describe the scalability of an algorithm whose count is 2n log₂ n + 5n.

CALCULATE IT | STUDENTS AND CLUBS

Calculate and explain the complexity of this task: for each of n students, inspect all m clubs with constant work per inspection, then make one extra pass over the students. Define both input sizes, give a work model and state the standard Big O. Then consider m = 3 and m = n separately.

Reveal an approach

The model is nm + n, giving O(nm + n) for non-negative input sizes. For m at least 1 this simplifies to O(nm). If m is a fixed 3, the work is 4n, giving O(n). If m = n, the work is n² + n, giving O(n²). The answer depends on which dimensions grow and their relationship.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.4.1 Big O and Scalability is coming soon. Complete the matching task and written questions in your exercise book.