COMP9123 — Week 3

Foundations & proof moves

Week 3 foundations sharpen the technical side of the lecture: how to order growth classes, how to separate time from space, and how the right maintained invariants make stack and queue operations stay fast.

Growth-order warm-upsQueue designADT augmentation

Ordering Growth Classes Without Guesswork

Tutorial 3 opens by forcing you to compare expressions like \( \sqrt{n}, n, n \log n, n^2, 2^n, n!, n^n \). The goal is not symbol pushing. The goal is to recognise which families dominate others as \(n\) gets large.

Core idea

Polynomial growth beats logarithmic growth, exponential growth beats polynomial growth, and factorial growth beats ordinary exponentials. Once you know the family, the rough ordering becomes much easier.

Family	Typical examples	How to think about it
Sublinear	\(\log n, \sqrt{n}\)	Grows, but much more slowly than scanning all items.
Linear / near-linear	\(n, n \log n\)	The usual territory of efficient algorithms on large inputs.
Polynomial	\(n^2, n^3\)	Often acceptable only for moderate input sizes.
Exponential and beyond	\(2^n, n!, n^n\)	Explodes quickly; usually means exhaustive combinatorial search.

Mini example from the tutorial spirit

function printFive(n)
    for i ← 1 to 5 do
        print('n')

This is \(O(1)\), not \(O(n)\), because the loop bound is a fixed constant 5 and does not scale with the input parameter.

Quick check

What is the asymptotic running time of printFive(n) from the tutorial?

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

\(O(n^2)\)

Time vs Space: Cost Is Not Only About Speed

The lecture deliberately pairs time-complexity examples with space-complexity examples so you do not fall into the habit of discussing runtime alone.

Core idea

Time complexity measures how long the work takes. Space complexity measures how much extra information must be stored. Good algorithmic judgment needs both.

Linear space

Storing one extra record per input item, like customer orders or browsing history, usually gives \(O(n)\) extra space.

Quadratic space

Storing pairwise relationships, such as all user-to-user comparisons, can produce \(O(n^2)\) memory growth.

Exponential space

Generating all combinations or candidate passwords can explode to \(O(2^n)\) storage or worse.

Practical lesson: two algorithms can have similar runtimes but very different memory costs. Week 3 wants you to keep those design axes separate.

Quick check

If an algorithm stores one helper record for each input element, what is the usual extra-space cost?

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

\(O(n^2)\)

Queue Invariants, O(1) Operations, and ADT Augmentation

The best Week 3 tutorial problems ask a design question, not just a coding question: what information should the ADT maintain so that useful operations stay cheap?

Core idea

Constant-time operations only stay constant time if the structure keeps the right distinguished references and summary data up to date.

Structure	What must be maintained	Why it matters
Stack on singly linked list	Reference to the head / top	Push and pop can happen at one end in \(O(1)\).
Queue on singly linked list	References to both front and rear	Enqueue and dequeue both avoid a traversal.
Queue with `getAverage()`	Size and running sum	The average becomes a constant-time query instead of a full scan.

1

Use one stack for newly enqueued items and one stack for items ready to dequeue.

2

When the dequeue stack is empty, pour all items from the enqueue stack into it. This reverses order exactly once.

3

Each element moves a bounded number of times, which is why the structure can still support efficient queue behaviour.

Why it matters. Good data-structure design is often about maintaining the right state so the expensive work is rare or controlled.

Quick check

What extra maintained information makes queue getAverage() a natural \(O(1)\) operation?

A sorted array copy of the queue

Only the rear pointer

The running sum together with the current size

A recursion stack

Quick checks

The Week 3 checkpoints now sit directly under the growth, space, and augmentation sections above so you can test each idea right after reading it.

Tutorial PDF review

Attempt the tutorial before looking at worked answers. The value of Week 3 is in forcing yourself to justify the representation choice, not just naming the right ADT.

Tutorial 3 checklist. Make sure you can do all of the following without hand-waving:

Problems 1–2 — order growth classes and justify the ranking, not just guess it.
Problems 3–4 — explain why stack push/pop and queue enqueue/dequeue can be \(O(1)\) on singly linked lists if the right ends are used and the right references are stored.
Problems 5–6 — analyse printFive as \(O(1)\) and stars as \(\Theta(n^2)\), giving both upper and lower reasoning for the second.
Problem 7 — design getAverage() by storing auxiliary state such as running sum and size, then explain correctness and runtime.
Problem 8 — implement a queue with two stacks and explain the time-cost story carefully.
Problem 9 — detect a palindrome in a singly linked list in \(O(n)\) time and \(O(1)\) extra space while restoring the list.
Problem 10 — write the balanced-parentheses algorithm cleanly using a stack.