Unit 9 · Introduction to Computer Science

Efficiency Analysis

CSC108H1 introduced big-O informally. Here it becomes a tool for choosing between the structures you have built: which operations each does cheaply, which expensively, and how to analyse a recursive function whose cost is not obvious from looking at it.

By the end you can

Define big-O in terms of growth, and say what it ignores.
Analyse loops, nested loops and recursive calls.
Compare the structures from Units 3, 4, 7 and 8 by operation.
Distinguish worst, average and amortised cost.

Why it matters & where it comes from

Why it exists

Every structure in this course is a trade-off. Analysis is how you make the trade deliberately rather than by habit, and it is the only way to compare two correct programs.

In the real world

A quadratic algorithm on a thousand items is fine and on a million is hopeless. Most performance problems in production are not slow code — they are the wrong growth rate discovered after the data grew.

Story & open questions

The notation is Bachmann's, from 1894 number theory. Knuth brought it into computing in 1976. Whether every problem verifiable in polynomial time is also solvable in polynomial time — P versus NP — remains open and carries a million-dollar prize.

What big-O means

Definition

A function is $O(g(n))$ if, beyond some input size, its cost is at most a constant multiple of $g(n)$. Informally: how the work grows as the input grows.

Constants are dropped: $3n$ and $n$ are both $O(n)$.

Lower-order terms are dropped: $n^2 + n$ is $O(n^2)$.

It describes an upper bound on growth, not a running time in seconds.

Constants matter in practice, just not in big-O

An $O(n)$ algorithm with a huge constant can lose to an $O(n^2)$ one on small inputs. Big-O tells you which wins eventually, which is the right question when data grows and the wrong one when it never will.

Analysing code

Rule Sequential adds, nested multiplies

python

for x in xs: ...        # O(n)
for y in xs: ...        # O(n)   - total still O(n)

for x in xs:            # O(n)
    for y in xs: ...    #   x O(n) = O(n^2)

Two passes are $2n$, which is $O(n)$. Nested passes multiply, and that is the difference that matters.

Look for hidden loops

python

out = []
for x in xs:
    if x not in out:        # this is a loop! O(len(out))
        out.append(x)

One visible loop, $O(n^2)$ total. The operations that hide a loop are in on a list, list.remove, list.insert(0, x), list.pop(0), slicing, and string concatenation. Each turns an enclosing loop quadratic.

Example Analysing recursion

Count the calls and multiply by the work per call.

python

def total(obj):           # nested list, n integers total
    if isinstance(obj, int):
        return obj
    return sum(total(item) for item in obj)

Each integer and each list is visited exactly once, and the work at each is constant. So $O(n)$ where $n$ counts every node in the structure.

python

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Two calls per level, depth $n$, so about $2^n$ calls. Exponential — and the reason is that the same subproblems are recomputed endlessly.

python

def total_rec(xs: list) -> int:
    if xs == []:
        return 0
    return xs[0] + total_rec(xs[1:])

$n$ calls, but xs[1:] copies the rest of the list each time. Copying $n$, then $n-1$, and so on gives $O(n^2)$ — hidden entirely inside the slice.

Comparing the structures

Rule The table worth knowing

Python list. Index $O(1)$; append $O(1)$; insert or delete at the front $O(n)$; search $O(n)$.

Linked list. Index $O(n)$; prepend $O(1)$; insert or delete at a known node $O(1)$; search $O(n)$.

Stack and queue. $O(1)$ per operation when implemented with the right end or with a linked list.

BST. Search, insert, delete $O(\log n)$ balanced, $O(n)$ worst case.

Dictionary and set. Lookup, insert, delete $O(1)$ on average — but no ordering.

Example Choosing from the table

Membership tested in a loop → set, not list. $O(n)$ instead of $O(n^2)$.

Repeated insertion at the front → linked list, not Python list.

Keys needed in sorted order → BST, not dictionary.

Indexing by position → Python list, not linked list.

Every one of these is a one-line change that alters the growth rate, which is why the table is worth memorising.

Worst, average, amortised

Definition

Worst case: the most expensive input of that size. The default when a complexity is quoted without qualification.

Average case: expected cost over typical inputs. Needs an assumption about what "typical" means.

Amortised: average cost per operation over a long sequence, where occasional expensive operations are paid for by many cheap ones.

Example Why append is amortised $O(1)$

A Python list keeps spare capacity. Most appends drop into a free slot, which is $O(1)$. When it fills, the list allocates a bigger block and copies everything — $O(n)$.

That copy happens rarely, and because the capacity roughly doubles, the cost of all the copies up to size $n$ adds to about $2n$.

Spread over $n$ appends, that is constant per operation. So append is amortised $O(1)$ even though individual calls can be $O(n)$.

Example Where average and worst diverge

BST search: $O(\log n)$ average with random insertions, $O(n)$ worst case with sorted ones. Unit 8's honest version.

Dictionary lookup: $O(1)$ average, $O(n)$ worst if every key collides. In practice the worst case never occurs, which is why the average is quoted.

Say which case you mean. "A dictionary is $O(1)$" is shorthand for the average, and the distinction matters when an adversary chooses the input.

Common pitfalls

• Writing $O(2n)$ or $O(n + 3)$. Drop constants: both are $O(n)$.
• Missing hidden loops inside list operations and slicing.
• Quoting BST or dictionary complexity without saying which case you mean.
• Assuming fewer lines means faster. A one-line comprehension can be quadratic.
• Optimising growth rate on data that will never be large. Sometimes $O(n^2)$ is the right answer.

Practice

Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.

Practice 1 · Read the loops

What is the complexity of two sequential loops over the same list?

Answer

$O(n)$. Sequential work adds and constants drop.

Practice 2 · Hidden cost

What is the complexity of building a list with if x not in out inside a loop?

Answer

$O(n^2)$. The membership test scans a growing list on every iteration.

Practice 3 · Fix it

How do you make that $O(n)$?

Answer

Track seen items in a set, where membership is $O(1)$ on average, while still appending to a list to preserve order.

Practice 4 · Slicing

Why is recursing with xs[1:] quadratic?

Answer

Each slice copies the remaining elements, so the copies total $n + (n-1) + \cdots$, which is $O(n^2)$.

Practice 5 · Structure choice

You need fast membership and fast sorted output. What do you use?

Answer

A BST gives both: $O(\log n)$ membership when balanced, and sorted output free from in-order traversal. A set is faster for membership but cannot produce order without sorting.

Practice 6 · Amortised

Explain why list.append is called amortised $O(1)$.

Answer

Most appends are constant time. Occasionally the list resizes and copies everything, which is $O(n)$, but because capacity doubles, those copies total about $2n$ over $n$ appends — constant on average.

Practice 7 · Tree traversal

What is the complexity of visiting every node of a tree with $n$ values?

Answer

$O(n)$. Each node is visited exactly once and the work per node is constant.

Practice 8 · When not to care

When is an $O(n^2)$ algorithm acceptable?

Answer

When $n$ is small and bounded, or when the simpler code is worth more than the speed. Choosing quadratic knowingly is fine; choosing it accidentally is not.

Expanded topic checklist

Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:

Big-O. Growth rates, dropping constants and lower-order terms.
Reading code. Sequential versus nested, and the operations that hide a loop.
Recursive analysis. Counting calls times work per call.
Case distinctions. Worst, average and amortised, and when each is the honest figure to quote.

Textbook/source alignment

The calendar names "analyzing the efficiency of programs". Check Quercus for the assigned exercises; complexity questions appear on every term test in this course.

Core idea map

Cost grows with input. Structures differ in which operations are cheap. Choosing one is choosing which operations you are willing to pay for, and analysis is how that choice gets made on evidence.

Study routine. State the big-O of every method you write, in its docstring where the course asks for it. Ten seconds each, and it turns analysis into a habit rather than an exam topic.

Deep practice extensions

Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.

Extension 1 · What is dropped

Why is $3n^2 + 5n$ written $O(n^2)$?

Guide

Constants and lower-order terms do not affect the growth rate, which is all big-O describes.

Extension 2 · Combining

How do sequential and nested loops combine?

Guide

Sequential add and collapse to the largest term; nested multiply.

Extension 3 · Hidden loops

Name three operations that are secretly $O(n)$.

Guide

x in a_list, list.pop(0), and slicing. Each makes an enclosing loop quadratic.

Extension 4 · Amortised versus average

How do they differ?

Guide

Amortised averages over a sequence of operations and is a guarantee. Average case averages over inputs and depends on an assumption about which inputs occur.

← Unit 08Binary search trees Unit 10 →Sorting & inheritance