Quick Sort: Worst Case, Randomized Version, and Sorting Example

STEP 1 - Given Data

• Array to sort: ${-2, 4, -3, 6, 12, 10, 11, 13, 9}$
• Number of elements: $n = 9$
• Marks: 10

STEP 2 - Solution

Part A: Worst Case of Quick Sort

Quick Sort selects a pivot and partitions the array into elements smaller and larger than the pivot, then recursively sorts each part.

Worst case occurs when the pivot chosen at every step is the largest or smallest element, so the partition is maximally unbalanced: one side has $n-1$ elements, the other has $0$.

This happens (using first/last element as pivot) when the array is already sorted or reverse sorted.

Recurrence: $$T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n)$$

Solving: $$T(n) = O(n) + O(n-1) + \dots + O(1) = O(n^2)$$

So worst case time complexity is $\mathbf{O(n^2)}$.

Part B: Randomized Quick Sort

Randomized Quick Sort picks the pivot randomly rather than always the first/last element.

RANDOMIZED-PARTITION(A, p, r):
    i = RANDOM(p, r)
    swap A[i] with A[r]
    return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r):
    if p < r:
        q = RANDOMIZED-PARTITION(A, p, r)
        RANDOMIZED-QUICKSORT(A, p, q-1)
        RANDOMIZED-QUICKSORT(A, q+1, r)

How it helps: Since the pivot is chosen uniformly at random, no fixed input pattern (sorted/reverse sorted) can force worst-case behavior consistently. The probability of repeatedly hitting the worst split is extremely small. The expected running time becomes $O(n \log n)$ for any input, though the theoretical worst case remains $O(n^2)$ (with negligible probability).

Part C: Sorting Using Quick Sort (Lomuto, last element as pivot)

Array: $[-2, 4, -3, 6, 12, 10, 11, 13, 9]$

Step 1: pivot = 9

Elements $< 9$: $-2, 4, -3, 6$; elements $\ge 9$: $12, 10, 11, 13$

$$[-2, 4, -3, 6,; \boxed{9},; 12, 10, 11, 13]$$

Recurse on $[-2, 4, -3, 6]$ and $[12, 10, 11, 13]$.

Step 2: Left $[-2, 4, -3, 6]$, pivot = 6

All ($-2, 4, -3$) $< 6$: $$[-2, 4, -3,; \boxed{6}]$$ Recurse on $[-2, 4, -3]$.

Step 3: $[-2, 4, -3]$, pivot = -3

Both $-2, 4 \ge -3$: $$[\boxed{-3},; -2, 4]$$ Recurse on $[-2, 4]$.

Step 4: $[-2, 4]$, pivot = 4

$-2 < 4$: $$[-2,; \boxed{4}]$$ Sorted. Left portion → $[-3, -2, 4, 6]$

Step 5: Right $[12, 10, 11, 13]$, pivot = 13

$12, 10, 11 < 13$: $$[12, 10, 11,; \boxed{13}]$$ Recurse on $[12, 10, 11]$.

Step 6: $[12, 10, 11]$, pivot = 11

$10 < 11$, $12 \ge 11$: $$[10,; \boxed{11},; 12]$$ Left $[10]$ and right $[12]$ are single elements → sorted. Right portion → $[10, 11, 12, 13]$

Final Combination

$$\underbrace{[-3, -2, 4, 6]}{\text{left}} ;; \boxed{9} ;; \underbrace{[10, 11, 12, 13]}{\text{right}}$$

Final Sorted Array

$$\boxed{[-3, -2, 4, 6, 9, 10, 11, 12, 13]}$$

Solving Recurrence Relations Using Master's Method

Master Method Framework

For $T(n) = aT\left(\frac{n}{b}\right) + f(n)$ with $a \geq 1$, $b > 1$:

Compute the critical exponent $\log_b a$ and compare $f(n)$ with $n^{\log_b a}$:

Given Data

• Recurrence 1: $T(n) = 2T(n/2) + n^3$, $n>1$; $T(1)=1$
• Recurrence 2: $T(n) = 2T(n/4) + 1$, $n>1$; $T(1)=1$

Problem 1: $T(n) = 2T\left(\dfrac{n}{2}\right) + n^3$

Parameters: $a = 2,\ b = 2,\ f(n) = n^3$

Critical exponent: $$\log_b a = \log_2 2 = 1 \implies n^{\log_b a} = n$$

Compare: $f(n) = n^3$ vs $n^1$

Since $n^3 = \Omega(n^{1+\epsilon})$ with $\epsilon = 2 > 0$, this is Case 3.

Regularity check: $$a,f!\left(\frac{n}{b}\right) = 2\left(\frac{n}{2}\right)^3 = \frac{n^3}{4} \leq c,n^3,\quad c=\tfrac14 < 1 \ \checkmark$$

Result: $$\boxed{T(n) = \Theta(n^3)}$$

Problem 2: $T(n) = 2T\left(\dfrac{n}{4}\right) + 1$

Parameters: $a = 2,\ b = 4,\ f(n) = 1 = n^0$

Critical exponent: $$\log_b a = \log_4 2 = \frac{1}{2} \implies n^{\log_b a} = \sqrt{n}$$

Compare: $f(n) = n^0$ vs $n^{1/2}$

Since $n^0 = O(n^{1/2 - \epsilon})$ with $\epsilon = \tfrac12 > 0$, this is Case 1.

Result: $$\boxed{T(n) = \Theta(\sqrt{n})}$$

Summary

Order Statistics Problem and Edit Distance

Part 1: Order Statistics Problem

Definition:

Given a set (or array) $A$ of $n$ elements drawn from a totally ordered set, the $i$-th order statistic is the $i$-th smallest element of $A$.

• Input: An array $A$ of $n$ elements and an integer $i$ where $1 \le i \le n$.
• Output: The element $e \in A$ that is greater than exactly $i-1$ other elements of $A$.

Special cases:

• $i = 1$ → minimum element
• $i = n$ → maximum element
• $i = \lfloor (n+1)/2 \rfloor$ → median

The selection problem is the general problem of finding the $i$-th order statistic, solvable in expected linear time $O(n)$ (randomized-select) or worst-case $O(n)$ (median-of-medians).

Part 2: Edit Distance between 'cat' and 'car'

Given Data

• $X = \text{"cat"}$, length $m = 3$
• $Y = \text{"car"}$, length $n = 3$
• Operation costs: insert = delete = replace = $1$

Recurrence

$$ dp[i][j] = \begin{cases} j & i = 0 \ i & j = 0 \ dp[i-1][j-1] & X[i] = Y[j] \ 1 + \min\big(dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1]\big) & X[i] \neq Y[j] \end{cases} $$

Filling the Table

Initialization: first row = $0,1,2,3$; first column = $0,1,2,3$.

Row i=1 (X='c'):

• $dp[1][1]$: c=c → $dp[0][0]=0$
• $dp[1][2]$: c≠a → $1+\min(2,0,1)=1$
• $dp[1][3]$: c≠r → $1+\min(3,1,2)=2$

Row i=2 (X='a'):

• $dp[2][1]$: a≠c → $1+\min(0,2,1)=1$
• $dp[2][2]$: a=a → $dp[1][1]=0$
• $dp[2][3]$: a≠r → $1+\min(2,0,1)=1$

Row i=3 (X='t'):

• $dp[3][1]$: t≠c → $1+\min(1,3,2)=2$
• $dp[3][2]$: t≠a → $1+\min(0,2,1)=1$
• $dp[3][3]$: t≠r → $1+\min(1,1,0)=1$

Final DP Table

Result

$$\boxed{\text{Edit Distance} = dp[3][3] = 1}$$

Interpretation: Only one replace operation is required - substitute 't' with 'r' to turn "cat" into "car".

Short Notes: Asymptotic Notations and Complexity Classes

a) Big Oh, Big Omega, and Big Theta

Big Oh O(g(n)) - Asymptotic Upper Bound

Big Oh notation gives the asymptotic upper bound of a function.

Definition: A function f(x) is said to be O(g(x)) if and only if there exist two positive constants c and x₀ such that:

For all x >= x₀ : f(x) <= c * g(x)

This means g(n) is the upper bound of f(n). The algorithm will never take more time than this bound.

Example: If f(n) = 3n² + 4n + 1, then:

• 3n² + 4n + 1 <= 14n² for all n >= 1
• Therefore, f(n) = O(n²) with c = 14, x₀ = 1

Big Omega Ω(g(n)) - Asymptotic Lower Bound

Big Omega notation gives the asymptotic lower bound of a function.

Definition: A function f(x) is said to be Ω(g(x)) if and only if there exist two positive constants c and x₀ such that:

For all x >= x₀ : f(x) >= c * g(x)

This means g(n) is the lower bound of f(n).

Example: If f(n) = 3n² + 4n + 1, then:

• 3n² + 4n + 1 >= 3n² for all n >= 1
• Therefore, f(n) = Ω(n²) with c = 3, x₀ = 1

Big Theta Θ(g(n)) - Asymptotic Tight Bound

Big Theta notation gives the asymptotically tight bound of a function.

Definition: A function f(x) is said to be Θ(g(x)) if and only if there exist three positive constants c₁, c₂ and x₀ such that:

For all x >= x₀ : c₁ * g(x) <= f(x) <= c₂ * g(x)

This means g(n) is both an upper and lower bound of f(n).

Example: If f(n) = 3n² + 4n + 1, g(n) = n², choose c₁ = 1, c₂ = 14, n₀ = 1:

• 1 * n² <= 3n² + 4n + 1 <= 14 * n² for all n >= 1
• Therefore, f(n) = Θ(n²)

b) Class P, Class NP, and NP-Complete

Class P (Polynomial Time)

• Class P is the set of all decision problems that can be solved by a deterministic algorithm in polynomial time O(n^k) for some constant k.
• These are considered tractable (efficiently solvable) problems.
• Examples: Sorting, searching, shortest path (Dijkstra's), GCD computation.

Class NP (Non-deterministic Polynomial Time)

• Class NP is the set of all decision problems for which a given solution (certificate) can be verified in polynomial time by a deterministic algorithm.
• NP does not necessarily mean the problem cannot be solved in polynomial time; it means verification is polynomial.
• Every problem in P is also in NP (P ⊆ NP), but whether P = NP is an unsolved problem in computer science.
• Examples: Boolean satisfiability (SAT), Hamiltonian cycle, Subset sum.

NP-Complete

• A problem X is NP-Complete if:

  1. X belongs to NP (its solution can be verified in polynomial time), AND
  2. Every other problem in NP can be reduced to X in polynomial time (X is NP-Hard).

• NP-Complete problems are the hardest problems in NP.

• If any NP-Complete problem can be solved in polynomial time, then all NP problems can be solved in polynomial time (i.e., P = NP).

• Examples: SAT problem, Travelling Salesman Problem (TSP), Knapsack problem, Graph Coloring.

Relationship Summary

P ⊆ NP
NP-Complete ⊆ NP
If P = NP, then all NP-Complete problems become P