Skip to content
CampusPrep
CS-402 · Analysis Design of Algorithm/Quick Revision Short Notes

Analysis Design of Algorithm (CS-402) - Unit 1 Short Notes

How unit 1 is examined

This unit covers algorithm basics, analysis, asymptotic notations, heap sort and the divide and conquer sorts and searches; recurrences, asymptotic notations, quick sort, merge sort, heap sort, binary search and Strassen carry the marks.

Algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>An algorithm is a finite sequence of well-defined, unambiguous steps that takes zero or more inputs and produces at least one output in a finite amount of time.</mark>

Key points.

  1. Every algorithm must be finite, so it terminates after a bounded number of steps.
  2. Every step must be definite, meaning precisely and unambiguously stated.
  3. It has zero or more inputs and at least one output.
  4. It must be effective, so each step is basic enough to be carried out exactly.

Designing algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Designing an algorithm means choosing a strategy for the problem and writing it as pseudocode, which is language-independent, step-wise text.

Key points.

  1. The main design strategies are divide and conquer, greedy, dynamic programming, backtracking and branch and bound.
  2. A good design is then proved correct and analysed for time and space.

Analyzing algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Analysis of an algorithm is the estimation of the time and space it needs, as a function of input size $n$, so that algorithms can be compared before they are coded.</mark>

Key points.

  1. Time complexity is the number of basic steps executed as a function of $n$; space complexity is the memory used by input, auxiliary variables and the recursion stack.
  2. Analysis is needed to compare two algorithms for the same problem independently of machine and language.
  3. It predicts resources and shows scalability: an algorithm fine for $n=100$ may be hopeless for $n=10^6$.
  4. Cases: best case is the minimum steps over inputs of size $n$, worst case is the maximum (an upper guarantee), average case is the expected steps over all inputs.
  5. Asymptotic analysis ignores constants and lower-order terms and keeps only the growth rate, expressed in $O$, $\Omega$, $\Theta$.
  6. Example: for $n=10^6$ sorted items, linear search needs up to $10^6$ comparisons and binary search about 20, so binary search is chosen.

Answer frame. Open with the definition of algorithm and its properties; define time and space complexity; develop the need; give the linear versus binary search example; close with best/average/worst cases, asymptotic notation, and selecting the best growth rate.

Asked: [7 marks] (Nov 2019) Define algorithm. Discuss how to analyse algorithms. Asked: [7 marks] (Jun 2020, Dec 2020, Nov 2023) What is the need of obtaining the time and space complexity measures of an algorithm? Justify with an example. / What do you mean by performance analysis of an algorithm?

Asymptotic notations

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Asymptotic notations describe the growth rate of an algorithm's running time for large $n$, ignoring constant factors and lower-order terms.</mark>

Notation Meaning Formal definition
$O(g)$ upper bound (worst) $f(n)\le c\,g(n)$ for all $n\ge n_0$, some $c>0$
$\Omega(g)$ lower bound $f(n)\ge c\,g(n)$ for all $n\ge n_0$
$\Theta(g)$ tight bound $c_1 g(n)\le f(n)\le c_2 g(n)$ for all $n\ge n_0$
$o(g)$ strict upper bound $f(n)<c\,g(n)$ for every $c>0$, $n\ge n_0$
$\omega(g)$ strict lower bound $f(n)>c\,g(n)$ for every $c>0$, $n\ge n_0$

Key points.

  1. Big-Oh gives an asymptotic upper bound, so $f(n)=O(g(n))$ means $f$ grows no faster than $g$; it is used for worst-case statements.
  2. Omega gives a lower bound, so $f$ grows at least as fast as $g$; it is used for best-case or problem lower bounds.
  3. Theta gives a tight bound and holds exactly when both $O(g)$ and $\Omega(g)$ hold.
  4. Little-o and little-omega are the strict versions: $2n=o(n^2)$ but $2n^2\ne o(n^2)$.
  5. Constants $c$ and $n_0$ are not unique; any valid pair proves the claim.
  6. Order of growth: $1<\log n<n<n\log n<n^2<n^3<2^n<n!$.

Example (Jun 2026). $f(n)=1000n^2+100n+6$. For $n\ge1$: $100n\le100n^2$ and $6\le6n^2$, so $f(n)\le1106\,n^2$. Hence $f(n)=O(n^2)$ with $c=1106$, $n_0=1$.

Example (Dec 2024). $f(n)=2n^2-4n+20$.

  • Upper: for $n\ge5$, $-4n+20\le0$, so $f(n)\le2n^2$; take $c_2=2$, $n_0=5$.
  • Lower: $n^2-4n+20>0$ for all $n$ (discriminant $16-80<0$), so $f(n)\ge n^2$; take $c_1=1$.
  • So $n^2\le f(n)\le2n^2$ for $n\ge5$, hence $f(n)=\Theta(n^2)$, also $O(n^2)$ and $\Omega(n^2)$.

Answer frame. Open with the definition; give the table with a sketch of $f$ between $c_1g$ and $c_2g$ for Theta; then Big-Oh with an example; close by saying $\Theta$ needs both bounds. For a numerical, state the definition, bound each term by the dominant term, give $c$ and $n_0$.

Pitfall: Writing the answer without $c$ and $n_0$; the bound is not proved until both are stated.

Asked: [14 marks] (May 2019, Jun 2020, Dec 2020, Nov 2023) What is an asymptotic notation? Explain the different notations used for algorithm complexity. / Short notes: Asymptotic notations. Asked: [14 marks] (Dec 2020, Jun 2022) Short notes (any two): a) Subset sort problem b) Big 'oh' notation; define Big Oh with example. Asked: [7 marks] (Dec 2024) Give the asymptotic bounds for $f(n)=2n^2-4n+20$ and represent in $\theta$ notation. Asked: [7 marks] (Jun 2026) For $f(n)=1000n^2+100n+6$ find the Big Oh notation.

Heap and heap sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A max-heap is a complete binary tree in which every parent is greater than or equal to its children, so the maximum sits at the root.</mark>

Key points.

  1. A heap is stored in an array; with 0-based indexing the children of $i$ are $2i+1$ and $2i+2$ and the parent is $\lfloor (i-1)/2\rfloor$.
  2. Heapify (sift-down) swaps a node with its larger child until the heap property holds, costing $O(\log n)$.
  3. Build-heap calls heapify on nodes $\lfloor n/2\rfloor-1$ down to 0 and costs $O(n)$.
  4. Heap sort builds a max-heap, then repeatedly swaps the root with the last unsorted element, shrinks the heap by one and heapifies the root.
  5. Time is $O(n\log n)$ in best, average and worst cases; space is $O(1)$, so it is in place but not stable.
Step 1: Build max-heap of A[0..n-1].
Step 2: For end = n-1 down to 1: swap A[0] and A[end].
Step 3: Heapify A[0] within A[0..end-1].
Step 4: Array is now ascending.

Example (66, 33, 40, 20, 50, 88, 60, 11, 77, 30, 45, 65). Heapify from index 5 down to 0 gives the heap below, then extract.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 580 262" width="580" height="262" role="img" aria-label="Max-heap after build-heap"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="476" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="476" y1="103" x2="432" y2="167"/><line class="e" x1="476" y1="103" x2="520" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">88</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">77</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">33</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">20</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">50</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">45</text><circle class="n" cx="476" cy="103" r="17"/><text class="t" x="476" y="103" dy=".35em" text-anchor="middle">66</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">65</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">40</text><circle class="n" cx="520" cy="167" r="17"/><text class="t" x="520" y="167" dy=".35em" text-anchor="middle">60</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Max-heap after build-heap</figcaption></figure>

Step Array (sorted part at the right)
Max-heap built 88 77 66 33 50 65 60 11 20 30 45 40
Extract 88 77 50 66 33 45 65 60 11 20 30 40 | 88
Extract 77 66 50 65 33 45 40 60 11 20 30 | 77 88
Extract 66 65 50 60 33 45 40 30 11 20 | 66 77 88
Extract 65, 60, 50 45 33 40 30 11 20 | 50 60 65 66 77 88
Remaining extractions 11 20 30 33 40 45 50 60 65 66 77 88

Sorted: 11, 20, 30, 33, 40, 45, 50, 60, 65, 66, 77, 88.

Answer frame. Open with the definition of heap (complete tree plus heap property); draw the tree of the given array after build-heap; show the array after each extraction; close with the sorted array and $O(n\log n)$.

Asked: [7 marks] (Nov 2019, Dec 2020, Jun 2022, Nov 2023) Sort using heap sort: 66, 33, 40, 20, 50, 88, 60, 11, 77, 30, 45, 65. / Sort (5, 8, 3, 9, 2, 10, 1, 45, 32) using heap sort (answer 1, 2, 3, 5, 8, 9, 10, 32, 45). / Explain heap; sort 81, 39, 10, 36, 45, 15, 55, 23, 91, 88, 12 (answer 10, 12, 15, 23, 36, 39, 45, 55, 81, 88, 91).

Introduction to divide and conquer technique

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Divide and conquer solves a problem by dividing it into smaller sub-problems of the same type, solving them recursively, and combining their solutions.</mark>

Key points.

  1. Divide splits the problem of size $n$ into $a$ sub-problems of size about $n/b$.
  2. Conquer solves each sub-problem recursively, using a direct solution when it is small enough.
  3. Combine merges the sub-solutions into the answer, and its cost is $f(n)$.
  4. The running time follows $T(n)=aT(n/b)+f(n)$.
  5. Examples are binary search, merge sort, quick sort and Strassen; advantages are simple code and efficiency, a drawback is recursion overhead.
  6. Greedy (Jun 2020 part ii) builds a solution by taking the locally best choice at every step, hoping it is globally optimal, as in knapsack and Dijkstra.

Answer frame. Open with the definition; write the three phases; give the recurrence $T(n)=aT(n/b)+f(n)$; list examples with complexities; close with advantages.

Asked: [7 marks] (Jun 2020) Short notes: i) Divide and Conquer technique ii) Greedy algorithm. Asked: [7 marks] (Jun 2022) Explain Divide and Conquer techniques.

Analysis, design and comparison of various algorithms based on this technique

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Master theorem. For $T(n)=aT(n/b)+f(n)$ with $a\ge1$, $b>1$, compare $f(n)$ with $n^{\log_b a}$:

  • $f(n)=O(n^{\log_b a-\epsilon})$ gives $T(n)=\Theta(n^{\log_b a})$.
  • $f(n)=\Theta(n^{\log_b a})$ gives $T(n)=\Theta(n^{\log_b a}\log n)$.
  • $f(n)=\Omega(n^{\log_b a+\epsilon})$ and $af(n/b)\le cf(n)$ gives $T(n)=\Theta(f(n))$.

Key points.

  1. Substitution method: guess the form of the solution, then prove it by induction, choosing the constant large enough.
  2. For a square-root recurrence, put $n=2^m$ so that $\sqrt n$ becomes $2^{m/2}$.
  3. Comparison of the divide and conquer algorithms:
Algorithm Recurrence Time Space
Binary search $T(n/2)+1$ $O(\log n)$ $O(1)$
Merge sort $2T(n/2)+n$ $\Theta(n\log n)$ $O(n)$
Quick sort $2T(n/2)+n$ average $O(n\log n)$ avg, $O(n^2)$ worst $O(\log n)$
Strassen $7T(n/2)+n^2$ $O(n^{2.81})$ $O(n^2)$

Solved recurrences.

  • $T(n)=2T(n/2)+n$: $a=2$, $b=2$, $f(n)=n=n^{\log_2 2}$, Master case 2, so $T(n)=\Theta(n\log n)$. $T(n)=\Theta(n\log n)$.
  • $T(n)=3T(n/3)+n$: guess $T(n)\le cn\log n$. Then $T(n)\le 3c\frac n3\log\frac n3+n=cn\log n-cn\log 3+n\le cn\log n$ whenever $c\ge 1/\log 3$; choose $c$ to also cover the base case. $T(n)=\Theta(n\log n)$.
  • $T(n)=T(\sqrt n)+C$, $n>4$: put $n=2^m$ and $S(m)=T(2^m)$, so $S(m)=S(m/2)+C$. Unfolding, $S(m)=C\log_2 m+S(1)$. Back-substituting, $T(n)=C\log_2\log_2 n+O(1)$. $T(n)=\Theta(\log\log n)$, since the sqrt is taken $\log\log n$ times before $n\le4$.
  • $T(n)=2T(\sqrt n)+\log n$, $n>4$: put $n=2^m$, $S(m)=T(2^m)$, so $S(m)=2S(m/2)+m$. By case 2, $S(m)=\Theta(m\log m)$. $T(n)=\Theta(\log n\cdot\log\log n)$.

Answer frame. Name the recurrence and method in the opening line; show $a$, $b$, $f(n)$ or the guess, induction step and choice of $c$; close with the bold $\Theta$ result.

Asked: [7 marks] (Nov 2023) Solve $T(n)=1$ for $n\le4$, $T(n)=T(\sqrt n)+C$ for $n>4$, using substitution. Asked: [7 marks] (Jun 2024) Obtain the asymptotic bound of $T(n)=3T(n/3)+n$ by substitution, in $\theta$ notation. Asked: [7 marks] (Jun 2025) Solve $T(n)=1$ for $n\le4$, $T(n)=2T(\sqrt n)+\log n$ for $n>4$, using substitution. Asked: [7 marks] (Jun 2024, Jun 2026) Solve the recurrence $T(n)=2T(n/2)+n$.

Binary search

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Binary search finds a key in a sorted array by comparing it with the middle element and discarding the half that cannot contain it.</mark>

Step 1: low = 0, high = n-1.
Step 2: While low <= high: mid = (low + high) / 2.
Step 3: If A[mid] == key return mid.
Step 4: If key < A[mid], high = mid - 1; else low = mid + 1.
Step 5: Return -1 (not found).

Key points.

  1. Divide: the middle element splits the array into two halves; conquer: search only one half; combine: nothing is needed.
  2. The array must be sorted, otherwise discarding a half is invalid.
  3. Recurrence: $T(n)=T(n/2)+O(1)$, because one comparison halves the problem.
  4. Solving: $T(n)=T(n/2^k)+k$, and $n/2^k=1$ gives $k=\log_2 n$, so $T(n)=O(\log n)$; the Master theorem gives the same ($a=1$, $b=2$, $f=1=n^0$).
  5. Best case is $O(1)$ when the key is at the first middle; worst case is $O(\log n)$ with about $\lfloor\log_2 n\rfloor+1$ comparisons, when the key is absent or at a leaf.
  6. Average case is $O(\log n)$ too, about $\log_2 n-1$ comparisons for a successful search.

Answer frame. Open with the divide and conquer idea; write the algorithm; give the recurrence and solve it; close with a best, average, worst table of $O(1)$, $O(\log n)$, $O(\log n)$.

Asked: [7 marks] (May 2019, Jun 2024, Jun 2026) Give the divide and conquer solution for binary search and analyse its complexity; analyse worst, average and best cases. Asked: [14 marks] (Jun 2024) Short notes on any two: a) Binary search algorithm and its time complexity, b) Single source shortest path, c) Parallel algorithms, d) NP Completeness.

Merge sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Merge sort divides the array into two halves, sorts each recursively, and merges the two sorted halves into one sorted array.</mark>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 360 198" width="360" height="198" role="img" aria-label="Recursion tree, n/2^k pieces at level k, each level costs n"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="256" y1="103" x2="212" y2="167"/><line class="e" x1="256" y1="103" x2="300" y2="167"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">n</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">n/2</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">n/4</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">n/4</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">n/2</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">n/4</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">n/4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Recursion tree, n/2^k pieces at level k, each level costs n</figcaption></figure>

MergeSort(A, l, r):
Step 1: If l >= r return.
Step 2: m = (l + r) / 2.
Step 3: MergeSort(A, l, m); MergeSort(A, m+1, r).
Step 4: Merge the two sorted halves using a temporary array.

Key points.

  1. Divide splits at the middle, conquer sorts each half recursively, and merge combines two sorted halves by repeatedly copying the smaller front element.
  2. Merging $n$ elements takes $\Theta(n)$, so $T(n)=2T(n/2)+\Theta(n)$.
  3. There are $\log_2 n$ levels each costing $n$, so $T(n)=\Theta(n\log n)$.
  4. Best, average and worst cases are all $\Theta(n\log n)$, because the split and merge work does not depend on the input order.
  5. Space is $O(n)$ for the temporary array; merge sort is stable but not in place.
  6. Since best case is $\Theta(n\log n)$ and worst case is $O(n\log n)$, we can say the time is $O(n\log n)$; more precisely it is $\Theta(n\log n)$, because $\Theta$ implies both $O$ and $\Omega$.

Example (22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3).

  • Split: [22 12 30 46 28 14] and [8 10 56 18 3], further into [22 12 30], [46 28 14], [8 10 56], [18 3] and pairs.
  • Merge: [12 22 30], [14 28 46], then [12 14 22 28 30 46]; [8 10 56], [3 18], then [3 8 10 18 56].
  • Final merge: 3, 8, 10, 12, 14, 18, 22, 28, 30, 46, 56.
  • Other list (20, 30, 15, 11, 35, 19, 12, 11, 55) gives 11, 11, 12, 15, 19, 20, 30, 35, 55.

Answer frame. Open with the definition and the three steps; write the algorithm; derive $T(n)=2T(n/2)+n$ and solve; for the numerical draw the split tree then the merge tree; close with the sorted list and $\Theta(n\log n)$. For the Jun 2025 question answer: best case is also $\Theta(n\log n)$, so yes we may say $O(n\log n)$.

Asked: [7 marks] (Jun 2020, Jun 2023) Explain / design merge sort and find its best, average and worst-case complexity. Asked: [7 marks] (Jun 2024, Dec 2024) Define Quicksort? Sort 22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3 using merge sort. / What is merge sort? Sort 20, 30, 15, 11, 35, 19, 12, 11, 55. Asked: [7 marks] (Jun 2025) The worst case of merge sort is $O(n\log n)$; what is its best case? Can we say the time is $O(n\log n)$?

Quick sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Quick sort picks a pivot, partitions the array so that smaller elements lie left and larger elements lie right of the pivot, then sorts the two parts recursively.</mark>

QuickSort(A, lo, hi):
Step 1: If lo >= hi return.
Step 2: pivot = A[lo]; i = lo+1; j = hi.
Step 3: Move i right while A[i] <= pivot; move j left while A[j] > pivot; swap if i < j; repeat.
Step 4: Swap pivot with A[j]; pivot is now in its final place.
Step 5: QuickSort(A, lo, j-1); QuickSort(A, j+1, hi).

Key points.

  1. The pivot ends in its final sorted position after partition, so no combine step is needed.
  2. Partition takes $\Theta(n)$ time.
  3. Best case: pivot splits evenly, $T(n)=2T(n/2)+n$, giving $\Theta(n\log n)$; average case is also $\Theta(n\log n)$.
  4. Worst case: the pivot is the smallest or largest element (sorted or reverse input with first-element pivot), $T(n)=T(n-1)+\Theta(n)$, giving $\Theta(n^2)$.
  5. When all elements are equal, this naive partition puts everything on one side, so $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$; stopping the scans on equal keys, or 3-way partition, gives $\Theta(n\log n)$ and $\Theta(n)$ respectively.
  6. Space is $O(\log n)$ for the stack; it is in place but not stable.

Example (36, 12, 85, 79, 46, 18, 92, 30, 28, 65, 72), first element as pivot.

Sub-list, pivot After partition
whole list, 36 18 12 28 30 36 46 92 79 85 65 72
18 12 28 30, pivot 18 12 18 28 30
28 30, pivot 28 28 30 (both placed)
46 92 79 85 65 72, pivot 46 46 92 79 85 65 72
92 79 85 65 72, pivot 92 72 79 85 65 92
72 79 85 65, pivot 72 65 72 85 79
85 79, pivot 85 79 85

Sorted: 12, 18, 28, 30, 36, 46, 65, 72, 79, 85, 92.

Other lists sort to 6, 10, 12, 23, 28, 33, 39, 67, 78, 87, 97; C, E, E, G, L, L, O; and 1, 7, 9, 12, 14, 15, 24, 31, 80.

Answer frame. For a numerical, state the pivot rule (first element) and partition rule, show each partition row, and give the sorted list with average $O(n\log n)$ and worst $O(n^2)$. For the algorithm question write the pseudocode, the three recurrences, then time and space.

Asked: [7 marks] (May 2019, Jun 2020, Jun 2023, Jun 2026) Apply quick sort to 36, 12, 85, 79, 46, 18, 92, 30, 28, 65, 72. / Steps for (23, 67, 12, 78, 33, 28, 97, 10, 6, 87, 39). / Trace for C, O, L, L, E, G, E. / Sort 15, 31, 1, 9, 80, 12, 14, 7, 24. Asked: [7 marks] (Nov 2019) Running time of quick sort when all elements of A have the same value. Asked: [7 marks] (Nov 2023) Give an algorithm for quick sort and analyse it.

Strassen's matrix multiplication

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Strassen's method multiplies two $n\times n$ matrices by dividing each into four $n/2\times n/2$ blocks and using 7 recursive multiplications instead of 8.</mark>

Formulas. With blocks $A_{ij}$, $B_{ij}$:

$$M_1=(A_{11}+A_{22})(B_{11}+B_{22}),\quad M_2=(A_{21}+A_{22})B_{11},\quad M_3=A_{11}(B_{12}-B_{22})$$

$$M_4=A_{22}(B_{21}-B_{11}),\quad M_5=(A_{11}+A_{12})B_{22},\quad M_6=(A_{21}-A_{11})(B_{11}+B_{12})$$

$$M_7=(A_{12}-A_{22})(B_{21}+B_{22})$$

$$C_{11}=M_1+M_4-M_5+M_7,\quad C_{12}=M_3+M_5,\quad C_{21}=M_2+M_4,\quad C_{22}=M_1-M_2+M_3+M_6$$

Key points.

  1. Ordinary multiplication uses three loops, giving $\Theta(n^3)$; the divide version uses 8 half-size multiplications, $T(n)=8T(n/2)+n^2=\Theta(n^3)$, so it gains nothing.
  2. Strassen uses 7 multiplications and 18 matrix additions or subtractions of size $n/2$, so $T(n)=7T(n/2)+O(n^2)$.
  3. Master theorem: $a=7$, $b=2$, $n^{\log_2 7}\approx n^{2.81}$ exceeds $f(n)=n^2$, so case 1 gives $T(n)=\Theta(n^{\log_2 7})\approx\Theta(n^{2.81})$.
  4. Since $2.81<3$, Strassen is asymptotically faster: for $n=1024$, $n^3\approx1.07\times10^9$ against $n^{2.81}\approx2.8\times10^8$.
  5. The gain is only asymptotic: 18 additions, a larger constant and extra memory make classical faster for small $n$; Strassen wins beyond a crossover of a few hundred (tuned code switches to classical below about 32-128).
  6. Pad with zeros if $n$ is not a power of 2.

Answer frame. Open with the definition and the ordinary $O(n^3)$ cost; write the four blocks, the seven $M_i$ and four $C_{ij}$; give the recurrence and its Master theorem solution; close with the comparison and the crossover remark.

Asked: [7 marks] (May 2019, Jun 2024) How can we prove that Strassen's matrix multiplication is advantageous over ordinary matrix multiplication? Asked: [7 marks] (Jun 2023) Discuss Strassen's matrix multiplication and derive its time complexity. Asked: [7 marks] (Dec 2024) Write an algorithm for matrix multiplication using Strassen's method. Asked: [7 marks] (Jun 2024) Discuss Strassen's and classical methods; when does Strassen outperform classical?

Last-minute revision

  1. $O$ is an upper bound, $\Omega$ a lower bound, $\Theta$ both; state $c$ and $n_0$.
  2. $1000n^2+100n+6=O(n^2)$ with $c=1106$, $n_0=1$; $2n^2-4n+20=\Theta(n^2)$.
  3. $T(n)=2T(n/2)+n$ and $3T(n/3)+n$ are $\Theta(n\log n)$; $T(\sqrt n)+C$ is $\Theta(\log\log n)$; $2T(\sqrt n)+\log n$ is $\Theta(\log n\log\log n)$.
  4. Binary search: $T(n/2)+1$, $O(\log n)$, best $O(1)$.
  5. Merge sort: $\Theta(n\log n)$ in all cases, space $O(n)$, stable.
  6. Quick sort: average $n\log n$, worst $n^2$ (sorted or all-equal input).
  7. Heap sort: build-heap $O(n)$, sort $O(n\log n)$, in place.
  8. Strassen: 7 multiplications, $7T(n/2)+n^2$, $n^{2.81}$ against $n^3$.

Memory hooks

  1. Big-Oh is a Ceiling, Omega is a floor, Theta is the room between.
  2. Merge sort: "split easy, merge hard"; quick sort: "partition hard, combine free".
  3. Strassen: 7 not 8, 18 additions, exponent 2.81.
  4. Sorted input is quick sort's worst case; all-equal keys too.

Coverage checklist

  • Algorithms: definition and four properties.
  • Designing algorithms: strategies and pseudocode.
  • analyzing algorithms: Nov 2019 define and analyse; Jun 2020, Dec 2020, Nov 2023 need of time and space.
  • asymptotic notations: May 2019, Jun 2020, Dec 2020, Nov 2023 notations; Dec 2020, Jun 2022 Big Oh; Dec 2024 theta; Jun 2026 Big Oh.
  • heap and heap sort: Nov 2019, Dec 2020, Jun 2022, Nov 2023 heap sort numericals.
  • Introduction to divide and conquer technique: Jun 2020, Jun 2022.
  • analysis, design and comparison of various algorithms based on this technique: Nov 2023, Jun 2024, Jun 2025, Jun 2026 recurrences.
  • binary search: May 2019, Jun 2024, Jun 2026 algorithm; Jun 2024 short note.
  • merge sort: Jun 2020, Jun 2023, Jun 2024, Dec 2024, Jun 2025.
  • quick sort: May 2019, Nov 2019, Jun 2020, Jun 2023, Nov 2023, Jun 2026.
  • strassen’s matrix multiplication: May 2019, Jun 2023, Jun 2024, Dec 2024.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in