Here's a complete, theory-focused answer for DAA Unit 1, covering all five topics.

1. Asymptotic Notations — Definitions

Asymptotic notation describes the growth rate of a function as the input size $n \to \infty$, ignoring constant factors and lower-order terms. Let $f(n)$ and $g(n)$ be non-negative functions.

(a) Big-O (Upper Bound)

$f(n) = O(g(n))$ iff there exist constants $c > 0$ and $n_0 \ge 1$ such that: $0 \le f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$ It gives an upper bound on growth. $g(n)$ grows at least as fast as $f(n)$.

• Example: $2n + 10 = O(n)$, also $O(n^2)$.
• $n = O(n^2)$ but $n^2 \ne O(n)$.

(b) Big-Omega / Ω (Lower Bound)

$f(n) = \Omega(g(n))$ iff there exist $c > 0$ and $n_0 \ge 1$ such that: $0 \le c \cdot g(n) \le f(n) \quad \text{for all } n \ge n_0$ It gives a lower bound on growth.

• Example: $2n^2 + 3n = \Omega(n^2)$, also $\Omega(n)$.

(c) Big-Theta / Θ (Tight Bound)

$f(n) = \Theta(g(n))$ iff there exist $c_1 > 0, c_2 > 0$ and $n_0 \ge 1$ such that: $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \text{for all } n \ge n_0$ Equivalently, $f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))$.

• Example: $3n^2 + 5n = \Theta(n^2)$.

(d) Little-o (Strict Upper Bound)

$f(n) = o(g(n))$ iff for every $c > 0$ there exists $n_0$ such that: $0 \le f(n) < c \cdot g(n) \quad \text{for all } n \ge n_0$ It means $f$ grows strictly slower than $g$; equivalently $\lim_{n\to\infty} f(n)/g(n) = 0$.

• Example: $n = o(n^2)$.

(e) Little-omega (Strict Lower Bound)

$f(n) = \omega(g(n))$ iff for every $c > 0$ there exists $n_0$ such that: $0 \le c \cdot g(n) < f(n) \quad \text{for all } n \ge n_0$ $f$ grows strictly faster than $g$; equivalently $\lim_{n\to\infty} f(n)/g(n) = \infty$.

• Example: $n^2 = \omega(n)$.

Quick relation table:

2. Recurrence Relations — Mathematical Treatment

A recurrence expresses the cost of a problem of size $n$ in terms of smaller subproblems. Solving it gives the total complexity.

Standard Form (Divide & Conquer)

$T(n) = a\,T(n/b) + f(n), \quad T(1) = \Theta(1)$

• $a$ = number of subproblems
• $n/b$ = size of each subproblem
• $f(n)$ = cost of divide + combine steps

Methods of Solving

(i) Substitution (Induction) Method

1. Guess the asymptotic form from the recurrence.
2. Verify by induction: assume $T(k) \le c \cdot g(k)$ for $k < n$, then show $T(n) \le c \cdot g(n)$.

(ii) Iteration (Recursion Tree) Method

Expand the recurrence repeatedly: $T(n) = a\,T(n/b) + f(n) = a^2\,T(n/b^2) + a\,f(n/b) + f(n) = \cdots$ Sum the levels until the base case; the sum over all levels gives the total cost.

(iii) Master Theorem (CLRS)

For $T(n) = a\,T(n/b) + f(n)$ with $a \ge 1$, $b > 1$, compare $f(n)$ with $n^{\log_b a}$:

• Case 1: If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$
• Case 2: If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$
• Case 3: If $f(n) = \Omega(n^{\log_b a + \epsilon})$ and $a\,f(n/b) \le c\,f(n)$ (regularity) for some $c < 1$, then $T(n) = \Theta(f(n))$

Intuition: the work is dominated either by the leaves (Case 1), evenly distributed (Case 2), or by the root/combine step (Case 3).

Examples:

• $T(n) = 2T(n/2) + n$ → $n^{\log_2 2}=n$, $f(n)=\Theta(n)$ → Case 2 → $T(n)=\Theta(n \log n)$ (Merge Sort).
• $T(n) = 2T(n/2) + 1$ → $f(n)=O(n^{1-\epsilon})$ → Case 1 → $T(n)=\Theta(n)$.
• $T(n) = 3T(n/4) + n^2$ → $n^{\log_4 3}\approx n^{0.79}$, $f(n)=n^2$ → Case 3 → $T(n)=\Theta(n^2)$.

3. Divide and Conquer — General Procedure

Divide and Conquer (D&C) solves a problem by breaking it into independent, smaller subproblems, solving them recursively, and merging results.

Three phases:

1. Divide — Split the problem of size $n$ into $a$ subproblems, each of size roughly $n/b$.
2. Conquer — Recursively solve each subproblem. If the subproblem is small enough (base case), solve directly.
3. Combine — Merge the subproblem solutions into a solution to the original problem.

General template:

D&C(A, n):    if n is small:        solve directly    else:        partition A into a subproblems        for each subproblem:            result = D&C(subproblem)        return combine(results)

Cost recurrence: $T(n) = a\,T(n/b) + f(n)$, solved via the Master Theorem.

Key property: subproblems must be independent (no overlap). If subproblems overlap, D&C is inefficient and Dynamic Programming is preferred.

Classic applications: Binary Search, Merge Sort, Quick Sort, Strassen's Matrix Multiplication, Closest Pair of Points, Maximum Subarray.

4. Sorting Algorithms — Algorithm & Analysis

(a) Merge Sort

Idea: Divide the array into two halves, recursively sort each, then merge the two sorted halves.

Algorithm:

MergeSort(A, l, r):    if l < r:        m = floor((l + r) / 2)        MergeSort(A, l, m)        MergeSort(A, m + 1, r)        Merge(A, l, m, r)

Merge step uses an auxiliary array and two pointers, taking $\Theta(n)$ time.

Analysis:

• Recurrence: $T(n) = 2T(n/2) + \Theta(n)$
• Master Theorem, Case 2 → $T(n) = \Theta(n \log n)$ (best, average, worst).
• Space: $\Theta(n)$ auxiliary (not in-place).
• Stable sort; works well on linked lists and external sorting.

(b) Quick Sort

Idea: Pick a pivot, partition the array so elements $<$ pivot go left and $>$ pivot go right, then recursively sort both sides.

Algorithm (Lomuto/Hoare partition):

QuickSort(A, l, r):    if l < r:        p = Partition(A, l, r)        QuickSort(A, l, p - 1)        QuickSort(A, p + 1, r)

Partition: choose pivot, rearrange so pivot is in its final sorted position; costs $\Theta(n)$.

Analysis:

• Worst case: $\Theta(n^2)$ — happens when pivot is always the smallest/largest (e.g., already sorted input with naive pivot). Recurrence $T(n) = T(n-1) + \Theta(n)$.
• Average case: $\Theta(n \log n)$. Recurrence $T(n) = 2T(n/2) + \Theta(n)$.
• Space: $O(\log n)$ stack on average, $O(n)$ worst.
• In-place (uses $O(1)$ extra space per level); not stable.
• Pivot strategies to avoid worst case: random pivot, median-of-three.

(c) Heap Sort

Idea: Build a max-heap, repeatedly extract the max and place it at the end of the array, then re-heapify.

Algorithm:

HeapSort(A, n):    BuildMaxHeap(A, n)          // O(n)    for i = n down to 2:        swap A[1] with A[i]     // move max to end        MaxHeapify(A, 1, i-1)   // restore heap

Heapify on a node of height $h$ costs $\Theta(h)$; Build-Heap costs $\Theta(n)$.

Analysis:

• Time: $\Theta(n \log n)$ in all cases (worst, average, best).
• Space: $O(1)$ extra (in-place).
• Not stable.
• Practical note: poor cache locality (random access in heap) makes it slower than Quick Sort in practice despite same asymptotic bound.

Comparison summary:

5. Dynamic Programming — Technique & Difference from Divide and Conquer

Dynamic Programming (DP)

DP is a technique for solving optimization problems with overlapping subproblems and optimal substructure. Instead of re-solving subproblems (as D&C does), DP stores solutions in a table (memoization or tabulation) and reuses them.

Two properties required:

1. Optimal Substructure — an optimal solution contains optimal solutions to subproblems.
2. Overlapping Subproblems — the same subproblem is encountered many times.

General procedure:

1. Characterize the form of an optimal solution.
2. Recursively define the optimal value.
3. Compute it bottom-up (tabulation) or top-down (memoization).
4. Construct the optimal solution from computed information.

Example — Matrix Chain Multiplication:

• Given $n$ matrices, find the parenthesization minimizing scalar multiplications.
• $m[i][j]$ = min cost to multiply matrices $i$ to $j$.
• $m[i][j] = \min_{i \le k < j} \{ m[i][k] + m[k+1][j] + p_{i-1}p_k p_j \}$.
• Time: $\Theta(n^3)$, Space: $\Theta(n^2)$.

Other classic DP problems: Longest Common Subsequence, Knapsack, All-Pairs Shortest Path (Floyd–Warshall), Single-Source Shortest Path (Bell