Data Structure and Algorithms

Pass path: Define ADT, define Big-O, Big-Omega, and Big-Theta notations, and identify best vs worst case complexity. Top path: Formally prove asymptotic bounds using limit definitions, compute closed-form operation counts from nested code loops, and evaluate space-time tradeoffs.

Part 1: Core Concepts (2 Marks)

• ★ Abstract Data Type (ADT): A mathematical specification of a data collection and the set of operations that can be performed on it, defined purely by its behavior and interface without specifying implementation details.
• ★ Asymptotic Notations:
  • Big-O ($O$): Formal mathematical upper bound. $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$.
  • Big-Omega ($\Omega$): Formal mathematical lower bound. $f(n) = \Omega(g(n))$ if $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$.
  • Big-Theta ($\Theta$): Asymptotically tight bound. $f(n) = \Theta(g(n))$ if $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$.
• ★ Space-Time Tradeoff: The principle that computational execution time can often be reduced by utilizing additional auxiliary memory storage (e.g., hash tables), or memory consumption reduced at the cost of slower execution.

Part 2: Structural Frameworks (10 Marks)

1. Mathematical Derivation of Asymptotic Bounds

When prompted to analyze the computational complexity of code snippets:

1. Loop Complexity Analysis Rules:
   • Single loop running $1$ to $n$: $O(n)$ linear time.
   • Nested loops running $1$ to $n$: $\sum_{i=1}^n \sum_{j=1}^n 1 = n^2 \implies O(n^2)$ quadratic time.
   • Loop variable multiplying or dividing by 2 ($i = i \times 2$): $\log_2 n$ iterations $\implies O(\log n)$ logarithmic time.
2. Formal Asymptotic Proof Example: Prove that $f(n) = 3n^2 + 5n + 2 = O(n^2)$.
   • We must find $c > 0$ and $n_0 \ge 1$ such that $3n^2 + 5n + 2 \le c \cdot n^2$ for all $n \ge n_0$.
   • For all $n \ge 1$:

     Swipe to see the full formula↔

     $$5n \le 5n^2 \quad \text{and} \quad 2 \le 2n^2$$
   • Therefore:

     Swipe to see the full formula↔

     $$3n^2 + 5n + 2 \le 3n^2 + 5n^2 + 2n^2 = 10n^2$$
   • Choosing $c = 10$ and $n_0 = 1$, the inequality holds strictly:

     Swipe to see the full formula↔

     $$3n^2 + 5n + 2 \le 10n^2 \quad \forall n \ge 1$$
   • Hence, $3n^2 + 5n + 2 = O(n^2)$. Q.E.D.

Part 3: Distinction Tables

Asymptotic Notations Comparison

Part 4: Worked Problems & Exam Traps

Problem 1 (Standard): Complexity from Nested Loop Code

Analyze the exact step count and Big-O time complexity:

int sum = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        sum++;
    }
}

• Step Count Derivation:

  Swipe to see the full formula↔

  $$\text{Total steps} = \sum_{i=0}^{n-1} i = 0 + 1 + 2 + \dots + (n-1) = \frac{(n-1)n}{2} = \frac{n^2 - n}{2}$$
• Asymptotic Classification:

  Swipe to see the full formula↔

  $$\frac{1}{2}n^2 - \frac{1}{2}n = O(n^2)$$

Students lose marks here because they assert that Big-O represents “worst case” and Big-Omega represents “best case”. Big-O, $\Omega$, and $\Theta$ are pure mathematical bounding notations applicable to any case (e.g., worst-case can have a $\Theta$ bound).