7.03e–7.03i - Efficiency and complexity | OCR A-Level Further Mathematics A

Two algorithms can reach the same answer with very different amounts of work. You will compare specified operation counts, calculate best, worst and average costs, recognise the hierarchy of growth orders, and use polynomial, logarithmic and exponential models to estimate running times.

Comparing a specified kind of work

Algorithm A needs $100n$ operations for an input of size $n$ , while algorithm B needs $n^2$ . Can the quadratic algorithm be quicker? Yes: at $n=10$ , the counts are $1000$ and $100$ . Later we will find exactly when that advantage disappears. First, make sure you are comparing the same kind of work.

You already know

An algorithm has precise instructions and a stopping condition. Its order describes dominant growth for large inputs; it does not give the exact operation count for a particular input.

A comparison tests two values against each other; a swap exchanges two stored values; a pass is one specified traversal of part or all of the data. These are different measures. Fewer passes need not mean fewer comparisons, and fewer comparisons need not mean fewer swaps.

Consider two algorithms searching for a target that appears exactly once. Algorithm L inspects a list from the left; algorithm R inspects it from the right. Each stops immediately on finding the target. Count one comparison for each entry tested against the target. These search instructions are not in the formula booklet.

Worked example 1: comparing searches on one input

Question. Algorithms L and R search the list $4,9,2,7,6,1$ for $7$ . Compare their efficiency using the number of comparisons.

Plan. Write the entries inspected in order, stopping at the first match in each direction.

\begin{aligned} L&:\quad4,9,2,7 && \text{four tests before stopping}\\ R&:\quad1,6,7 && \text{three tests before stopping} \end{aligned}

Why this step? Entries beyond the match are not tested, so the list length alone does not determine this count.

Answer. L uses $4$ comparisons and R uses $3$ . R is more efficient by this measure for this input.

Check. The target is fourth from the left and third from the right; $4+3=6+1$ .

Worked example 2 changes only the target. The algorithms stay the same, but the better result can reverse.

Worked example 2: a different target

Question. Compare L and R when searching the same list $4,9,2,7,6,1$ for $9$ .

Plan. Count the entries inspected from each end until $9$ is reached.

\begin{aligned} L&:\quad4,9 && 2\text{ comparisons}\\ R&:\quad1,6,7,2,9 && 5\text{ comparisons} \end{aligned}

Why this step? Efficiency in a particular case depends on where the required information lies, not just on the algorithm's name.

Answer. L is more efficient for this input: $2<5$ comparisons.

Check. The two positions satisfy $2+5=7$ , again one more than the list length.

This does not establish that either direction is better on every possible input. A claim about a specific list is narrower than a claim about general growth.

Exam tip

If a question specifies comparisons, give comparison counts and use them in the conclusion. A statement about passes or a general order does not answer that comparison.

The next list puts the target near one end, so count from the correct starting point in each algorithm.

Counting the worst case

A maximum cost must allow the input that makes the algorithm do the most work, even if that input is unusual.

Worst-case time complexity

For a specified problem size $n$ , $T(n)$ is the maximum run-time, or maximum count of a specified basic operation, over permitted inputs of that size. An operation count can be used as a model of run-time when its cost is treated as constant.

A search for the largest entry by scanning a list always needs $n-1$ comparisons: the first entry starts as the current largest, and each of the remaining entries is compared with it. A search for a target might stop sooner, but its worst case is $n$ comparisons if the target is last or absent. Neither count is printed in the formula booklet; derive it from the instructions.

Nested loops need more care. “For each” below means carrying out the inner instruction for every stated integer value. Count only the stated comparison, not the loop administration.

Worked example 3: comparing distinct pairs

Question. An algorithm has these instructions: for $i=1,2,\ldots,n$ , compare entry $i$ with each entry $j$ for $j=1,2,\ldots,i-1$ . Find its comparison count and order.

Plan. Count comparisons for each value of $i$ , then sum the resulting integers.

\begin{aligned} i=1,2,3,\ldots,n&:\quad0,1,2,\ldots,n-1 && \text{inner-loop counts}\\ T(n)&=\sum_{r=1}^{n-1}r=\frac{n(n-1)}2 && \text{integer sum}\\ &=\frac12n^2-\frac12n && \text{identify the dominant term} \end{aligned}

Why this step? The inner loop does not run $n$ times for every $i$ ; its length grows from $0$ to $n-1$ .

Answer. $T(n)=n(n-1)/2$ , of order $O(n^2)$ . Every input has this count, so it is also the worst-case count.

Check. For $n=6$ , $0+1+2+3+4+5=15=6(5)/2$ .

Worked example 4 changes only the inner-loop endpoint. Including $j=i$ adds one comparison for each outer-loop value.

Worked example 4: including the diagonal

Question. The algorithm instead uses $j=1,2,\ldots,i$ . Find its comparison count and order.

Plan. Replace the inner counts $0,1,\ldots,n-1$ by $1,2,\ldots,n$ .

\begin{aligned} T(n)&=1+2+\cdots+n && \text{new inner counts}\\ &=\frac{n(n+1)}2=\frac12n^2+\frac12n && \text{sum and expand} \end{aligned}

Why this step? The additional $n$ comparisons change the exact count but do not change its dominant power.

Answer. $T(n)=n(n+1)/2$ , again of order $O(n^2)$ .

Check. At $n=6$ , the new count is $21$ , exactly $6$ more than $15$ .

The sum formula is recalled from the standard-sums lesson. It is not a separate formula for nested loops: the instructions decide what must be summed.

Watch out

Wrong: two loops automatically mean exactly $n^2$ operations. Right: count the inner work for each outer value. Two full loops each of length $n$ give $n^2$ ; triangular ranges give a different exact count, though they can have the same order.

For the next algorithm, the extra work is specified explicitly rather than being hidden in the loop bounds.

Best, worst and typical cases

“Typical” needs a model for which inputs occur; averaging the best and worst counts works only when that averaging is justified.

For a target appearing once in a list of length $n$ , left-to-right search has best count $1$ , worst count $n$ , and count $r$ when the target is in position $r$ . If all positions are equally likely, each of those $n$ counts has probability $1/n$ .

Mean search cost for equally likely positions

If a target is present exactly once and is equally likely to be in any of $n$ positions, the mean comparison count is

\overline{C}=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}

This result depends on both the search rule and the stated distribution of target positions.
Not in the formula booklet: learn it.

The average is over inputs, not over repeated runs of a deterministic algorithm on the same input. The same input follows the same path each time.

Worked example 5: averaging all positions

Question. A list contains $6$ entries and one target. Its position is equally likely to be any of the six positions. A left-to-right search stops at the target. Find the best, worst and mean comparison counts.

Plan. List the possible counts and average them with equal weights.

\begin{aligned} C_{\min}&=1 && \text{target first}\\ C_{\max}&=6 && \text{target last}\\ \overline C&=\frac{1+2+3+4+5+6}{6}=\frac{21}{6}=3.5 && \text{equal probabilities} \end{aligned}

Why this step? The target's position determines the number of comparisons, so the mean position is the mean cost.

Answer. Best $1$ , worst $6$ , mean $3.5$ comparisons.

Check. Pair the positions: $1+6=2+5=3+4=7$ , giving mean $7/2$ . A mean need not be an integer.

Worked example 6 changes only the assumption that the target is certainly present. An unsuccessful search must inspect every entry.

Continue this lesson.

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

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.03e–7.03i - Efficiency and complexity

Comparing a specified kind of work

Counting the worst case

Best, worst and typical cases

Continue this lesson.

Learn faster with Nova