2.3.1 - Algorithm efficiency and Big O | OCR A-Level Computer Science

An algorithm's resource needs depend on both the amount of data and the operations it performs. You will derive growth from steps, distinguish cases, read complexity graphs, and compare time with auxiliary memory under explicit assumptions.

Choose an input size and a cost model

Time and space complexity

Time complexity describes how an algorithm's work grows with input size. Space complexity describes how its storage needs grow. State whether space includes the input and output or only auxiliary working storage.

Define n first: it might be the number of records, array elements or tree nodes. The number of bits in an integer would be a different input-size measure.

A cost model states which operations have unit cost. For these examples, assume fixed-size numbers, constant-cost arithmetic/comparisons, constant-cost access to an array element by index, and constant-cost retrieval of its length. Count a selected basic operation, such as an element comparison, rather than seconds. This model does not claim that arithmetic on arbitrarily large Python integers has constant cost or that every list operation does.

Consider a loop that compares each of n elements with a limit. It makes n element comparisons, plus loop-control work proportional to n. Counting only the comparisons is enough to reveal the same linear growth. Allocating an output copy of all n elements also requires storage proportional to n; a loop using only an index and counter has fixed auxiliary state.

Empirical timing measures seconds for a particular implementation. Repeat tests on the same hardware with comparable inputs and separate noise from a consistent trend. Include setup or preprocessing when it is required for the task. Measurements reveal constants and practical effects; an operation analysis predicts growth without depending on that computer. A test at one small size cannot establish a general growth class.

Use Big O to describe a growth bound

Big O is a growth bound

Big O gives an asymptotic upper bound: a cost is O(f(n)) if, for all sufficiently large n, it is at most a fixed constant times f(n). State the counted resource and input case separately.

If a count is $3n+8$ , then for $n\geq1$ it is at most $11n$ , so it is $O(n)$ . The added 8 and multiplied 3 do not change the linear growth class.

For $2n^2+5n+4$ , the quadratic term eventually dominates. Since the lower-order terms can also be bounded by constant multiples of $n^2$ , the count is $O(n^2)$ . This simplification describes growth; it does not say those terms consume no time in a real run.

Technically a linear cost is also $O(n^2)$ , because a quadratic function supplies a looser upper bound. When comparing algorithms here, give the tightest class established by the analysis, as is conventional in these exercises. Big O by itself does not specify best, average or worst case, and is not an exact count or stopwatch prediction.

Fixed repeated work is constant: $O(1)$ means the chosen cost is bounded independently of n. It can be one instruction or a fixed hundred; it does not mean zero work. For example, reading one stated array position is constant under our indexed-access model even when the whole input array contains n elements.

State which inputs a complexity describes

Different inputs of the same size can make an algorithm perform different work. Best case is the least work among permitted inputs of that size; worst case is the greatest. Average case is expected work under a stated distribution of inputs, not the midpoint of best and worst by definition.

For a linear search that stops at the first equal item, count equality comparisons. For $n\geq1$ , a match at index 0 gives one comparison: best-case $O(1)$ . A match at the last index or an absent target gives n: worst-case $O(n)$ . With empty input, the count is zero; that boundary does not describe the large-n growth class.

Suppose the target occurs exactly once and is equally likely to occupy any of the n positions. Possible comparison counts are 1,2,…,n, each with probability 1/n. Their average is $(1+2+\cdots+n)/n=(n+1)/2$ , hence $O(n)$ . For n = 6 this gives 3.5 comparisons on average; an expected value need not be an integer performed by one run. If absence has probability p, with the same uniform successful-position assumption, the average is $pn+(1-p)(n+1)/2$ . It is still linear for fixed p, but the numerical average changes.

An algorithm that always checks every element has n comparisons in best and worst cases. Cases differ only when the control flow or data-dependent work differs. Worst-case analysis is useful for a response-time bound; average-case claims need evidence for the assumed workload, especially when inputs are adversarial or heavily biased.

Derive growth from repetition and shrinking input

The number of repetitions, rather than the number of loop keywords, determines growth. A loop visiting n elements once gives $O(n)$ . Two loops run one after the other, each visiting n elements, give 2n visits, still $O(n)$ . Two nested loops each running n times perform n visits for each of n outer iterations, giving $n^2$ and $O(n^2)$ .

Polynomial growth has a fixed power, such as $n^2$ or $n^3$ . For an inner loop running i times at outer values i = 1,…,n, the count is $1+2+\cdots+n=n(n+1)/2$ , still quadratic. An inner loop fixed at five repetitions instead gives 5n, linear. Inspect the actual bounds before classifying nested loops.

Use this ungraded counter experiment to test that distinction. Each increment counts one execution of an inner body; it does not measure all Python instructions or elapsed seconds. The two counters represent different loop shapes, rather than two solutions to one problem.

Investigate which loop bound grows

{"exercise_id":"h446-2.3.1-loop-count-experiment","task_version":"1","runtime_profile":"python-console-v1","original_filename":"main.py","file_mode":"fresh","code":"def body_counts(n):\n pairs = 0\n fixed = 0\n for i in range(n):\n for j in range(n):\n pairs += 1\n for i in range(n):\n for j in range(3):\n fixed += 1\n return pairs, fixed\n\nprint(body_counts(3))\n","instructions":"Predict both counts for n=3, then run. Change the call to n=6: predict which count doubles and which quadruples, then check. Add calls with n=0 and n=1. Finally change range(3) to range(n), predict the effect at n=6, and run. Restore range(3) and explain why two nested loops need not imply quadratic growth. These examples assume n is a non-negative integer.","files":[]}

Logarithmic growth arises when a remaining problem is repeatedly divided by a fixed factor. With a positive integer m initially n, repeating m = m // 2 until m is zero takes $\lfloor\log_2 n\rfloor+1$ iterations. For n = 8, m changes 8 → 4 → 2 → 1 → 0 in four iterations. Each doubling of n adds roughly one step, rather than doubling the steps. Other fixed logarithm bases change only a constant factor, so the class is $O(\log n)$ .

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Computer systems (01)

Algorithms and programming (02)

Programming project skills (03)

2.3.1 - Algorithm efficiency and Big O

Choose an input size and a cost model

Use Big O to describe a growth bound

State which inputs a complexity describes

Derive growth from repetition and shrinking input

Continue this lesson.

Learn faster with Nova