Algorithmic Complexity

Context: FIT1008_MOC, FIT2004_MOC · the measurement foundation — input size, the RAM cost model, time complexity, per-operation cost, best/worst/average cases FIT2004 emphasis: distinguish total from auxiliary space (extra beyond the input — in-place $\equiv O(1)$ auxiliary); quote the tightest ($\Theta$) bound available. Input size is often bit-length — for a number $k$, $n=\lceil {\log }_2(k+1)\rceil$, not $k$.

Quick Revision

• 🎯 Objective: measure the resource (time/space) as a function of input size $n$ ➔ the question is scalability as $n\to \infty$.
• 📦 Core Components: input size $n$ (often bit-length!) | RAM unit-cost steps | time complexity $T(n)$ | case (best/worst/avg/amortised).
• ⚡ Key Constraint: unqualified “complexity” = worst case; the RAM unit-cost assumption breaks for variable-size keys ($\times \text{CompEq}$).

📝 Core

1. The Resource Question

• What it measures ➔ how cost grows with input size — time (elementary ops) or space (peak memory).
• Function of $n$ ➔ stated as $T(n)$, not a single number, because we care how it scales.
• Time–space trade-off ➔ extra memory buys speed (memoisation, hash tables) and vice-versa.

2. Input Size $n$ (“Big” Defined)

• Type-dependent ➔ collection’s element count | string’s chars | graph’s $|V|$ and $|E|$.
• Bit-length trap ➔ a number $k$ has size $\lceil {\log }_2(k+1)\rceil \approx {\log }_{2}k$, not $k$; halving $k$ to $1$ takes $\Theta (\log k)$ steps, i.e. $\Theta (\text{bits})$.
• Pseudo-polynomial ➔ a loop running $k$ times is $O(2^n)$ in true size (Knapsack $O(nW)$, still NP-hard).
• A BOUNDED parameter is a constant ➔ if the spec caps a parameter ($n\le 10^6$, $\text{arr}[i]<2^{32}$), it contributes $\Theta (1)$ and vanishes from the bound — the cap makes it independent of input size, not merely small.
• Which symbols are free ➔ before quoting a bound, list which parameters can grow without limit; a bound may only be expressed in those. The output size can be one ➔ Output-Sensitive Complexity.

3. Running Time & RAM Model

• Abstraction ➔ Random-Access Machine — each elementary op = 1 unit, $O(1)$ random access.
• Portability ➔ step count $T(n)$ is machine-independent ⟹ "$\Theta (n^2)$" portable, “3 ms” not.
• Declare the unit-cost assumption ➔ ”$+$ is $O(1)$” holds only for machine-word operands; on values whose bit-length grows with $n$ an addition costs $\Theta (\text{bits})$ ➔ iterative Fibonacci is $\Theta (n)$ word ops but $\Theta (n^2)$ bit ops, since $F(n)=\Theta ({\phi }^n)$ occupies $\Theta (n)$ bits ➔ Fibonacci Sequence. The model also breaks for external-memory effects.

4. Time Complexity $T(n)$ & Step Cost

• Counting rules ➔ statement $=1$ | sequence sums | if = test + branch | loop = body × iters | recursion = recurrence.
• CompEq factor ➔ a step is $O(1)$ only for fixed-size keys; length-$m$ strings ⟹ $O(n\log n)\cdot \text{CompEq}$.
• swap is $O(1)$ ➔ 3 copies; choose a sort minimising the expensive op.

5. Best / Worst / Average Case

• Definitions ➔ at fixed $n$: $W=\max$, $B=\min$, $A={\mathbb{E}}_{\mathcal{D}}[\text{cost}]$, with $B\le A\le W$.
• Best ≠ worst only on short-circuit ➔ requires an if/break/early return, else best=worst (selection sort).
• Average ≠ amortised ➔ average needs a distribution; amortised is a worst-case-sequence guarantee with no probability.

6. Space: Total vs Auxiliary (FIT2004 quoting standard)

• The lecture’s split ➔ space complexity $=$ input space $+$ auxiliary space, reported separately because only the second is the algorithm’s choice. Total space is always $\Omega (n)$ for an $n$-element input, so it never discriminates.
• Auxiliary space ➔ any memory beyond the input — the number quoted in a complexity table; in-place $\equiv$ $O(1)$ auxiliary.
• The three iterative reference cases ➔ find_min(arr) keeps one variable ⟹ input $\Theta (n)$, auxiliary $O(1)$, in-place · build_list(n) takes a number and allocates $n$ slots ⟹ input $O(1)$, auxiliary $\Theta (n)$ (no recursion, still $\Theta (n)$ — output counts) · iterative binary_search ⟹ auxiliary $O(1)$.
• Recursion stack counts ➔ auxiliary $\ge$ max live frame chain $=\Theta (\text{depth})$, never $\Theta (\text{total calls})$; balanced recursion gives $\Theta (\log n)$ frames against $\Theta (n)$ for peeling one element — the same split that decides time in Divide and Conquer ➔ Analysing Recursive Algorithms (Time and Auxiliary Space). Shrinking frames of size $n,n/2,n/4,\dots$ sum to $<2n=\Theta (n)$, not $\Theta (n\log n)$, by the $r=\frac{1}{2}$ bound in Geometric Series.
• Time $\ge$ auxiliary space — always ➔ memory must be allocated and written before it counts, and each cell costs $\ge 1$ step ⟹ an algorithm quoting $\Theta (n)$ auxiliary cannot be $o(n)$ in time.
• Tightest bound ➔ quote $\Theta$ when best $=$ worst; reserve $O$ for a genuine upper-bound-only claim.

⚙️ Core Implementation

🔹 Step-counting & the input-size gotcha

counting rules + bit-length trap

# T(n) counting (RAM model):
def bubble_sort(the_list):
    n = len(the_list)                       # 2 steps
    for _ in range(n-1):                    # outer: n-1
        for i in range(n-1):                # inner: n-1
            if the_list[i] > the_list[i+1]: # 3 steps
                swap(the_list, i, i+1)      # 7 steps
# T(n) = 13n^2 - 22n + 12  ->  O(n^2)
 
size = k.bit_length()      # == ceil(log2(k+1)) ~ log2 k   (a NUMBER's size)
len([1,2,3,5,8])           # 5   (a collection's size = element count)

💡 Common Mistake: Exact polynomial is accurate but useless ➔ report $O(n^2)$; a loop running $k$ times on number $k$ is $O(2^n)$ (since $n\approx {\log }_{2}k$), not $O(n)$.

🔹 Cost of a step & best/worst short-circuit

swap $O(1)$ + insertion-sort's best/worst gap

def swap(a, i, j):
    tmp = a[i]; a[i] = a[j]; a[j] = tmp      # always 3 copies => O(1)
 
# Insertion sort inner loop — the source of the best/worst split:
while i >= 0 and a[i] > temp:   # sorted -> stops at once (BEST, O(n) total)
    a[i + 1] = a[i]             # reverse -> runs k times (WORST, O(n^2))
    i -= 1

💡 Common Mistake: Best case ≠ “small input” ➔ both fix size $n$ and differ by arrangement; if comparison costs $O(m)$, multiply every bound by $m$.

⚖️ Core Decision Matrix

(Best / Average / Worst time, with the worst-case trigger.)

Algorithm	Best	Average	Worst	Trigger of worst
Bubble Sort II	$O(n)$	$O(n^2)$	$O(n^2)$	reverse-sorted
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	always (no short-circuit)
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	reverse-sorted
Quick Sort	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	min/max pivot
Hash Table	$O(1)$	$O(1)$	$O(n)$	all keys collide

When It Flips: quote worst for guarantees (real-time/adversarial), average for typical (quicksort, hashing), best rarely. Average ≠ amortised — average assumes a distribution (fails on skewed inputs); amortised is a hard worst-case-sequence guarantee.

📊 Exam Execution Trace

Applied Exercise

Problem: Show why an $O(nW)$ Knapsack DP is pseudo-polynomial, not polynomial.

$$\text{size of }W={\log }_{2}W\text{ bits}\Rightarrow O(nW)=O\left(n{2}^{{\log }_{2}W}\right)=\text{exponential in the encoding length of }W$$

Final Extracted Output: polynomial in the value $W$ but exponential in its bit-length ⟹ pseudo-polynomial (why Knapsack stays NP-hard).

✍️ Practice

Practice 1: CountBits(x) sets bits=1 then halves x while x>1; CountTotalBits(arr[1..n]) sums CountBits over the array. Give the $\Theta$ complexity when (a) $|arr|=n$, $0\le arr[i]\le 2^m-1$ · (b) same but $1\le n\le 10^6$ · (c) $|arr|=n$, $0\le arr[i]\le 2^{32}-1$.

• Hint: First cost one CountBits, then ask which of $n$ and $m$ is actually allowed to grow.

Answer

• Inner cost ➔ halving $x$ until $x\le 1$ runs $\lfloor {\log }_{2}x\rfloor$ times ⟹ $\Theta (\text{bit-length})$, capped at $\Theta (m)$.
• (a) $\Theta (nm)$ ➔ $n$ calls × $\Theta (m)$; both parameters unbounded, so both appear.
• (b) $\Theta (m)$ ➔ $n\le 10^6$ is a constant cap ⟹ $n=\Theta (1)$ ⟹ it drops out.
• (c) $\Theta (n)$ ➔ $arr[i]<2^{32}$ caps bit-length at $32=\Theta (1)$ ⟹ each call $\Theta (1)$.
• Why: A cap kills a parameter ➔ asymptotics describe growth, and a quantity that cannot grow contributes a constant factor — exactly what $\Theta$ discards. This is why 32/64-bit arithmetic is quoted $O(1)$ while big-integer arithmetic is not.

🧠 Active Recall

Distinguish worst-case, average-case, and amortised complexity, stressing each assumption.

• Hint: Each makes a different assumption.

Answer

• Short answer: Worst = max, no assumption; average = expectation over a distribution; amortised = worst-case sequence ÷ length, no probability.
• Why: Guarantee vs model ➔ amortised $O(1)$ append is a guarantee; average $O(1)$ hash lookup assumes good hashing.

Why is " $\Theta (n^2)$" portable but "runs in 3 ms" is not?

• Hint: RAM-model machine-independence.

Answer

• Short answer: $\Theta (n^2)$ is a property under the RAM model ⟹ identical step count across machines/compilers.
• Why: Folded constants ➔ “3 ms” folds in CPU speed, compiler, and input — none generalise.

Why do selection sort's best and worst cases coincide while quicksort's diverge?

• Hint: Short-circuit vs input-dependent pivot.

Answer

• Short answer: selection sort never early-terminates ⟹ cost depends only on $n$ ⟹ best=worst=$\Theta (n^2)$.
• Why: Pivot quality ➔ quicksort’s cost depends on the input (median $\Theta (n\log n)$, min/max $\Theta (n^2)$), so its cases separate.

Merge Sort is called an $O(n)$-space sort and Quick Sort an in-place one, yet both allocate. Justify both labels precisely.

• Hint: Auxiliary, and count the live stack chain.

Answer

• Short answer: auxiliary space is what is quoted. Merge sort needs a $\Theta (n)$ scratch array; quicksort partitions inside the array, leaving only the recursion stack, $O(\log n)$ when the smaller side recurses first.
• Why: Live chain, not total calls ➔ sibling calls execute sequentially, so only one root-to-leaf path of frames exists at once; “in-place” means $O(1)$ auxiliary excluding that stack — which is why quicksort’s label survives its $O(\log n)$ frames but degrades to $\Theta (n)$ on a worst-case pivot.

If each comparison costs $O(m)$ but each swap is $O(1)$, does merge sort or selection sort scale better?

• Hint: Weight ops by their true cost.

Answer

• Short answer: merge sort $\Theta (nm\log n)$ vs selection sort $\Theta (n^{2}m)$ ⟹ merge sort wins.
• Why: Comparison-dominated ➔ the $m$-amplified comparison cost dominates, so selection sort’s $\Theta (n)$ swap-thrift doesn’t help.