Algorithm Analysis and Sorting Techniques

Introduction to Algorithm

Algorithm is a finite sequence of well-defined, computer-implementable instructions to solve a

computational problem or perform a calculation. An algorithm provides a systematic approach
to problem-solving with the following characteristics:[1][2]

Key Properties

●​ Finiteness: Must terminate after finite number of steps

●​ Definiteness: Each step must be clearly defined

●​ Input: Zero or more inputs from a specified set

●​ Output: One or more outputs with specified relation to inputs

●​ Effectiveness: Each operation must be basic enough to be performed exactly

Algorithm Types

●​ Greedy Algorithm: Makes locally optimal choices at each step[1][2]

●​ Divide and Conquer: Breaks problems into smaller subproblems, solves recursively, then
combines solutions[2][1]

●​ Dynamic Programming: Solves problems by breaking into overlapping subproblems and

storing solutions[2]

Growth of Functions

Growth of functions describes how an algorithm's resource requirements (time/space) scale

with input size. The mathematical foundation uses asymptotic analysis to classify algorithm
efficiency.[3][4]

Asymptotic Notation Formulas

Big O Notation (Upper Bound)

 ​
Definition: There exist constants and such that:​

Omega Notation (Lower Bound)

​
Definition: There exist constants and such that:​

Theta Notation (Tight Bound)

Definition: is both and ​

Common Growth Orders

Notation Name Example

O(1) Constant Array access

O(log n) Logarithmic Binary search

O(n) Linear Linear search

O(n log n) Linearithmic Merge sort

O(n²) Quadratic Bubble sort

O(2ⁿ) Exponential Tower of Hanoi

Master's Theorem

Master's Theorem solves recurrence relations of the form:[5][6][7]​

Where:

●​ : Number of subproblems
 ●​ : Factor by which problem size reduces

●​ : Cost of work done outside recursive calls

Three Cases

Case 1: for

Case 2:

Case 3: for and regularity condition

Master Theorem Examples

Recurrence Parameters Case Solution

T(n) = 2T(n/2) + n a=2, b=2, f(n)=n Case 2 Θ(n log n)

T(n) = T(n/2) + n² a=1, b=2, f(n)=n² Case 1 Θ(n²)

T(n) = 3T(n/4) + n² a=3, b=4, f(n)=n² Case 3 Θ(n²)

Sorting Algorithms
Time complexity growth comparison of sorting algorithms

Quick Sort

Approach: Divide-and-conquer algorithm that partitions array around a pivot element.[8][9][10]

Algorithm Steps

1.​ Choose pivot element (typically last element)

2.​ Partition array: elements < pivot on left, elements > pivot on right

3.​ Recursively apply quicksort to left and right subarrays

4.​ No explicit combine step needed

Pseudocode

algorithm quicksort(A, lo, hi)​

if lo < hi then​
p := partition(A, lo, hi)​
quicksort(A, lo, p-1)​
 quicksort(A, p+1, hi)​
​
algorithm partition(A, lo, hi)​
pivot := A[hi]​
i := lo - 1​
for j := lo to hi-1​
if A[j] <= pivot then​
i := i + 1​
swap A[i] with A[j]​
swap A[i+1] with A[hi]​
return i + 1​

Time Complexity

●​ Best Case: - Balanced partitions

●​ Average Case: - Random pivots

●​ Worst Case: - Already sorted array with poor pivot choice

Space Complexity: - Recursive call stack

Heap Sort

Approach: Comparison-based sorting using binary heap data structure.[11][12][13]

Algorithm Steps

1.​ Build max-heap from unsorted array

2.​ Swap root (maximum) with last element

3.​ Reduce heap size and heapify root

4.​ Repeat until heap is empty

Pseudocode

algorithm heapsort(A)​
buildMaxHeap(A)​
for i := length(A) down to 2​
 swap A[^1_1] with A[i]​
heapSize := heapSize - 1​
maxHeapify(A, 1)​
​
algorithm buildMaxHeap(A)​
for i := floor(length(A)/2) down to 1​
maxHeapify(A, i)​
​
algorithm maxHeapify(A, i)​
left := 2*i​
right := 2*i + 1​
largest := i​
if left <= heapSize and A[left] > A[largest]​
largest := left​
if right <= heapSize and A[right] > A[largest]​
largest := right​
if largest ≠ i​
swap A[i] with A[largest]​
maxHeapify(A, largest)​

Time Complexity

●​ All Cases: - Guaranteed performance

●​ buildMaxHeap:

●​ Each heapify:

Space Complexity: - In-place sorting

Counting Sort

Approach: Non-comparison sorting for integers with limited range.[14][15][16]

Algorithm Steps

1.​ Find maximum value k in input array

2.​ Create counting array of size k+1

3.​ Count frequency of each element

 4.​ Calculate cumulative counts (prefix sum)

5.​ Place elements in output array using counts

Pseudocode

algorithm countingSort(A, k)​

C := array of size k+1 initialized to 0​
B := array of size length(A)​
​
// Count frequencies​
for i := 1 to length(A)​
C[A[i]] := C[A[i]] + 1​
​
// Calculate cumulative counts​
for i := 1 to k​
C[i] := C[i] + C[i-1]​
​
// Place elements in sorted order​
for i := length(A) down to 1​
B[C[A[i]]] := A[i]​
C[A[i]] := C[A[i]] - 1​
​
return B​

Time Complexity: where k is range of input

Space Complexity: for counting array

Stability: Yes - preserves relative order of equal elements

Shaker Sort (Cocktail Sort)

Approach: Bidirectional bubble sort that traverses array in both directions.[17][18][19][20]

Algorithm Steps

1.​ Traverse left to right, moving largest element to end

 2.​ Traverse right to left, moving smallest element to beginning

3.​ Reduce working range and repeat until no swaps occur

Pseudocode

algorithm shakerSort(A)​
swapped := true​
start := 0​
end := length(A) - 1​
​
while swapped​
swapped := false​
​
// Forward pass (left to right)​
for i := start to end-1​
if A[i] > A[i+1]​
swap A[i] with A[i+1]​
swapped := true​
end := end - 1​
​
if not swapped​
break​
​
// Backward pass (right to left) ​
swapped := false​
for i := end down to start+1​
if A[i] < A[i-1]​
swap A[i] with A[i-1]​
swapped := true​
start := start + 1​

Time Complexity

●​ Best Case: - Already sorted

●​ Average Case: - Random order

●​ Worst Case: - Reverse sorted

Space Complexity: - In-place sorting

Stability: Yes - maintains relative order

Complexity Comparison Table

Algorithm Best Case Average Case Worst Case Space Stable

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

Counting Sort O(n+k) O(n+k) O(n+k) O(k) Yes

Shaker Sort O(n) O(n²) O(n²) O(1) Yes

Key Insights

●​ Quick Sort: Fastest average case but poor worst-case performance[21][22]

●​ Heap Sort: Guaranteed O(n log n) performance, preferred for real-time systems[11][12]

●​ Counting Sort: Linear time for small integer ranges, not comparison-based[14][16]

●​ Shaker Sort: Slight improvement over bubble sort, educational value primarily​

Asymptotic Notation and Substitution Method

Asymptotic Notation

Asymptotic notation describes the limiting behavior of functions as input size approaches
infinity, providing a mathematical framework for algorithm analysis.[116][117][118]

Formal Definitions

Big O Notation (Upper Bound)

 ​
Definition: There exist positive constants and such that:​

Interpretation: grows no faster than asymptotically.[117][118]

Omega Notation (Lower Bound)

​
Definition: There exist positive constants and such that:​

Interpretation: grows at least as fast as asymptotically.[118][117]

Theta Notation (Tight Bound)

​
Definition: There exist positive constants and such that:​

Interpretation: grows exactly like asymptotically.[117][118]

Asymptotic notation relationships and bounds visualization

Asymptotic Notation Properties

Property Big O Big Ω Big Θ

Transitivity If f ∈ O(g) and g ∈ O(h), If f ∈ Ω(g) and g ∈ Ω(h), If f ∈ Θ(g) and g ∈ Θ(h),
then f ∈ O(h) then f ∈ Ω(h) then f ∈ Θ(h)

Reflexivity f ∈ O(f) f ∈ Ω(f) f ∈ Θ(f)

Symmetry Not symmetric Not symmetric If f ∈ Θ(g), then g ∈ Θ(f)

Little Notations

Little o Notation (Strict Upper Bound)

​
Definition: For every positive constant , there exists such that:​
Little omega Notation (Strict Lower Bound)

​
Definition: For every positive constant , there exists such that:​

Practical Examples

Example 1: Polynomial Analysis

Function:

Big O Analysis:

●​ For :

●​ Therefore: with

Omega Analysis:

●​ For :

●​ Therefore: with

Theta Analysis:

●​ Since and

●​ Therefore: with

Example 2: Linear Function

Function:

Analysis:

●​ For :

●​ For :

●​ Therefore: with
Substitution Method for Recurrence Relations

The substitution method solves recurrences through educated guessing followed by

mathematical proof via induction.[119][120][121][122]

Method Steps

Step 1: Generate Guess

●​ Intuitive Approach: Analyze recurrence structure

●​ Iterative Substitution: Expand recurrence several times to identify pattern

●​ Similar Problems: Use known solutions for analogous recurrences

Step 2: Prove by Induction

●​ Base Case: Verify guess holds for initial conditions

●​ Inductive Hypothesis: Assume guess holds for smaller values

●​ Inductive Step: Prove guess holds for general case using hypothesis

Substitution Method Examples

Example 1: Divide and Conquer Recurrence

Recurrence: ,

Step 1 - Guess: for some constant

Step 2 - Proof by Induction:

Base Case: For :

●​

●​ Need:

●​ Choose

●​ Let
Inductive Hypothesis: Assume for all

Inductive Step:​

​
​

Since , we have

Therefore: , confirming

Example 2: Linear Recurrence

Recurrence: ,

Step 1 - Guess: (arithmetic series sum)

Step 2 - Proof by Induction:

Base Case: ✓

Inductive Hypothesis: Assume

Inductive Step:​

​
 ​

Therefore:

Iterative Substitution Method

When direct guessing is difficult, iterative substitution reveals patterns by expanding the
recurrence.[123][124][125]

Example: ,

Expansion Process:​

Pattern Recognition:​
After substitutions:​

Geometric Series Formula:​

Base Case Resolution:​

When , we have :​

Simplification:

●​

●​

Since and :​

Advanced Substitution Techniques

Strong Induction

For recurrences depending on multiple previous terms, use strong induction:[126]

Example: Fibonacci-like recurrence

Strong Inductive Hypothesis: Assume property holds for all , not just

Variable Substitution

For complex recurrences, substitute :[123]

Example:

●​ Let , so

●​ Substitute:

●​ Transform to:
Method Comparison

Method Best Applications Complexity Success Rate

Substitution (Guess & When intuition available Medium High if guess correct
Check)

Iterative Substitution Linear recurrences Low High

Master Theorem Divide & conquer Low Limited scope

T(n)=aT(n/b)+f(n)

Generating Functions Counting problems High Very high

Characteristic Equation Linear homogeneous Medium High

Common Guessing Strategies

Pattern Recognition

●​ Linear growth: Guess

●​ Divide by 2: Often

●​ Tree-like: Usually

Substitution Verification

1.​ Prove upper bound:

2.​ Prove lower bound:

3.​ If , then

The substitution method remains the most general technique for solving recurrences, limited
only by the analyst's ability to generate appropriate guesses.​

Dynamic Programming and Advanced Algorithms

Introduction to Dynamic Programming

Dynamic Programming (DP) is both a mathematical optimization method and algorithmic

paradigm developed by Richard Bellman in the 1950s. It solves complex optimization problems
by breaking them into simpler subproblems and storing solutions to avoid recomputation.[191][192]

Key Components

Optimal Substructure

An optimal solution to a problem contains optimal solutions to its subproblems.[191][193]

Overlapping Subproblems

The same subproblems are solved multiple times in a naive recursive approach.[193][194][195]

Dynamic Programming Approaches

Approach Method Advantages Disadvantages

Memoization Top-down recursion with Natural recursive Function call overhead

caching structure

Tabulation Bottom-up iterative No recursion overhead Must solve all

solution subproblems

Principle of Optimality

Definition: An optimal policy has the property that whatever the initial state and initial decision
are, the remaining decisions must constitute an optimal policy with regard to the state resulting
from the first decision.[196][197][198]
Dynamic Programming process and Principle of Optimality flowchart

Mathematical Formulation

For a multi-stage decision process:​

Where:

●​ : Value function at stage in state

●​ : Immediate reward for action in state

●​ : Next state after taking action

Bellman Equation

The fundamental recursive relationship in dynamic programming:​

Single Source Shortest Path - Bellman-Ford Algorithm

The Bellman-Ford algorithm computes shortest paths from a single source vertex to all other
vertices in a weighted graph with possible negative edge weights.[199][200][201]

Algorithm Formula

Relaxation Operation:​

Pseudocode

algorithm BellmanFord(G, source)​

// Step 1: Initialize distances​
for each vertex v in [Link]​
distance[v] := infinity​
predecessor[v] := null​
distance[source] := 0​
​
// Step 2: Relax all edges |V| - 1 times​
for i := 1 to |[Link]| - 1​
for each edge (u,v) in [Link]​
if distance[u] + weight(u,v) < distance[v]​
distance[v] := distance[u] + weight(u,v)​
predecessor[v] := u​
​
// Step 3: Check for negative cycles​
for each edge (u,v) in [Link]​
if distance[u] + weight(u,v) < distance[v]​
return "Negative cycle detected"​
​
return distance, predecessor​

Complexity Analysis

[199][200]
●​ Time Complexity:

●​ Space Complexity:

●​ Negative Cycle Detection: Yes

Example Execution

Graph: Vertices {0,1,2,3,4}, Edges with weights

Iteration dist dist dist dist dist

Initial 0 ∞ ∞ ∞ ∞

1 0 -1 4 ∞ 1

2 0 -1 2 1 1

3 0 -1 2 -2 1

All Pairs Shortest Paths - Johnson's Algorithm

Johnson's Algorithm efficiently computes shortest paths between all pairs of vertices in a
sparse graph with possible negative edge weights but no negative cycles.[202][203][204]

Algorithm Steps

1.​ Augmentation: Add new vertex with zero-weight edges to all vertices

2.​ Reweighting: Use Bellman-Ford from to compute potential function

3.​ Transform weights:

4.​ Apply Dijkstra: Run Dijkstra's algorithm from each vertex on transformed graph

Mathematical Foundation

Reweighting Formula:​

Correctness Theorem: The shortest path in the original graph equals the shortest path in the
reweighted graph.[203]

Pseudocode

algorithm Johnson(G)​
// Step 1: Create augmented graph G'​
G' := G with new vertex s​
for each vertex v in [Link]​
 add edge (s,v) with weight 0 to G'​
​
// Step 2: Compute potential function​
if BellmanFord(G', s) returns "negative cycle"​
return "negative cycle detected"​
else​
h := distance array from BellmanFord​
​
// Step 3: Reweight edges​
for each edge (u,v) in [Link]​
w'(u,v) := w(u,v) + h[u] - h[v]​
​
// Step 4: Run Dijkstra from each vertex​
for each vertex u in [Link]​
distance[u] := Dijkstra(G', u)​
for each vertex v in [Link]​
distance[u][v] := distance[u][v] - h[u] + h[v]​
​
return distance​

Complexity Analysis

[203][204]
●​ Time Complexity:

●​ Space Complexity:

●​ Best for: Sparse graphs where

Comparison with Floyd-Warshall

Algorithm Time Complexity Space Best For Negative Cycles

Johnson's O(V²log V + VE) O(V²) Sparse graphs Detects

Floyd-Warshall O(V³) O(V²) Dense graphs Detects

Longest Common Subsequence (LCS)

LCS finds the longest subsequence common to two sequences without requiring consecutive
elements.[205][206][207][208]
Recurrence Relations

Base Cases:​

Recursive Formula:

𝐿𝐶𝑆[𝑖][𝑗] = {𝐿𝐶𝑆[𝑖 − 1][𝑗 − 1] + 1 𝑖𝑓 𝑋[𝑖 − 1] = 𝑌[𝑗 − 1] 𝑚𝑎𝑥(𝐿𝐶𝑆[𝑖 − 1][𝑗], 𝐿𝐶𝑆[𝑖][𝑗 − 1]) 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Algorithm Steps

1.​ Initialize: Create (m+1)×(n+1) table with zeros

2.​ Fill Table: Apply recurrence relation

3.​ Backtrack: Trace path to construct actual LCS

Pseudocode

algorithm LCS_Length(X, Y)​

m := length(X)​
n := length(Y)​
​
// Initialize LCS table​
LCS := array[0..m][0..n]​
for i := 0 to m​
LCS[i][^3_0] := 0​
for j := 0 to n​
LCS[^3_0][j] := 0​
​
// Fill table using recurrence​
for i := 1 to m​
for j := 1 to n​
if X[i-1] = Y[j-1]​
LCS[i][j] := LCS[i-1][j-1] + 1​
else​
LCS[i][j] := max(LCS[i-1][j], LCS[i][j-1])​
​
return LCS[m][n]​

Example: X = "ABCDGH", Y = "AEDFHR"

 ε A E D F H R

ε 0 0 0 0 0 0 0

A 0 1 1 1 1 1 1

B 0 1 1 1 1 1 1

C 0 1 1 1 1 1 1

D 0 1 1 2 2 2 2

G 0 1 1 2 2 2 2

H 0 1 1 2 2 3 3

Result: LCS = "ADH", Length = 3

Complexity Analysis

[205]
●​ Time Complexity:

●​ Space Complexity: (can be optimized to )

●​ Applications: DNA sequence analysis, file comparison, version control

Huffman's Code

Huffman coding constructs optimal prefix codes for data compression using a greedy
algorithm.[209][210][211]

Optimality Criterion

Minimize Average Code Length:​

Where:

●​ : Frequency of character

●​ : Length of codeword for character

Algorithm Steps
 1.​ Create leaf nodes for each character with frequencies

2.​ Build min-heap of all leaf nodes

3.​ Extract two minimum frequency nodes

4.​ Create internal node with frequency = sum of children

5.​ Repeat until heap contains only root

Pseudocode

algorithm HuffmanCoding(characters, frequencies)​

n := length(characters)​
heap := new MinHeap()​
​
// Step 1: Create leaf nodes​
for i := 1 to n​
node := new Node(characters[i], frequencies[i])​
[Link](node)​
​
// Step 2: Build Huffman tree​
while [Link]() > 1​
left := [Link]()​
right := [Link]()​
​
merged := new Node(null, [Link] + [Link])​
[Link] := left​
[Link] := right​
​
[Link](merged)​
​
root := [Link]()​
return generateCodes(root)​
​
algorithm generateCodes(node, code = "", codes = {})​
if [Link]()​
codes[[Link]] := code​
return codes​
​
generateCodes([Link], code + "0", codes)​
generateCodes([Link], code + "1", codes)​
 return codes​

Example: Characters {a,b,c,d,e,f} with frequencies {5,9,12,13,16,45}

Huffman Tree Construction:

1.​ Combine a(5) + b(9) = 14

2.​ Combine c(12) + d(13) = 25

3.​ Combine (14) + e(16) = 30

4.​ Combine (25) + (30) = 55

5.​ Combine f(45) + (55) = 100

Final Codes:

Character Frequency Code Code Length Total Bits

f 45 0 1 45

c 12 100 3 36

d 13 101 3 39

a 5 1100 4 20

b 9 1101 4 36

e 16 111 3 48

Properties and Bounds

Entropy Lower Bound:​

Huffman Optimality:​

Complexity Analysis

[209]
●​ Time Complexity:
 ●​ Space Complexity:

●​ Optimality: Produces minimum average codeword length among all prefix codes

Algorithm Comparison Summary

Algorithm Problem Type Time Complexity Space Key Feature

Bellman-Ford Single-source O(VE) O(V) Handles negative

shortest path weights

Johnson's All-pairs shortest O(V²log V + VE) O(V²) Efficient for sparse

path graphs

LCS Sequence O(mn) O(mn) Dynamic

alignment programming
classic

Huffman Optimal encoding O(n log n) O(n) Greedy algorithm

These algorithms demonstrate different paradigms - dynamic programming (Bellman-Ford,

LCS), combined approaches (Johnson's), and greedy methods (Huffman) - all unified by the
principle of optimality in constructing optimal solutions from optimal subproblems.​

String Matching and Advanced Optimization

Problems
String Matching

Introduction to String Matching

Finding occurrences of a pattern string within a text string .

●​ Input: Text of length , pattern of length

●​ Output: All indices such that

Applications

●​ Text search (e.g., grep)

●​ DNA sequence analysis

●​ Plagiarism detection

●​ Network intrusion detection (signature matching)

1. Naive Algorithm

Approach: Check each alignment by direct character comparison.

Pseudocode

for i from 0 to n-m​

j := 0​
while j < m and T[i+j] = P[j]​
j := j + 1​
if j = m​
report match at i​

Time Complexity

●​ Worst case:

●​ Best case (no matches):

Example

Text = “ABABABC”, Pattern = “ABABC”

i Comparisons Match?

0 5 Yes

1 1 No

2 5 Yes

2. Rabin–Karp Algorithm
Approach: Rolling hash to compare hash values before character checks.

Hash Function

Treat substring as number in base :​

●​ : alphabet size

●​ : large prime

Rolling Hash Update

Pseudocode

H_p := hash(P)​
H_t := hash(T[0..m-1])​
for i from 0 to n-m​
if H_t = H_p​
if T[i..i+m-1] = P​
report match at i​
if i < n-m​
H_t := (d*(H_t - T[i]*d^(m-1)) + T[i+m]) mod q​
if H_t < 0 then H_t += q​

Complexity

●​ Average case:

●​ Worst case (hash collisions):

3. Knuth–Morris–Pratt (KMP) Algorithm

Approach: Precompute longest proper prefix-suffix (LPS) to skip comparisons.

LPS Array
Pseudocode

// Preprocessing​
computeLPS(P, m):​
LPS[0] := 0​
len := 0, i := 1​
while i < m​
if P[i] = P[len]​
len := len + 1​
LPS[i] := len​
i := i + 1​
else if len ≠ 0​
len := LPS[len-1]​
else​
LPS[i] := 0​
i := i + 1​
​
// Search​
KMPSearch(T, P):​
computeLPS(P, m)​
i := 0, j := 0​
while i < n​
if P[j] = T[i]​
i := i + 1, j := j + 1​
if j = m​
report match at i - j​
j := LPS[j-1]​
else if j ≠ 0​
j := LPS[j-1]​
else​
i := i + 1​

Complexity

●​ Time:

●​ Space:
4. Boyer–Moore Algorithm

Approach: Scan from right to left using two heuristics: bad-character and good-suffix.

Bad-Character Heuristic

Let last occurrence function:​

​
Shift distance when mismatch at text position :​

Good-Suffix Heuristic

Compute shift based on matched suffix table.

Pseudocode Sketch

preprocessBadChar(P)​
preprocessGoodSuffix(P)​
i := 0​
while i ≤ n - m​
j := m - 1​
while j ≥ 0 and P[j] = T[i+j]​
j := j - 1​
if j < 0​
report match at i​
i := i + goodSuffixShift(0)​
else​
i := i + max(badCharShift(j, T[i+j]), goodSuffixShift(j))​

Complexity

●​ Average case: comparisons

●​ Worst case:

Chained Matrix Multiplication

Given chain of matrices with dimensions .

Objective

Minimize scalar multiplication cost:​

DP Recurrence

for i from 1 to n​
cost[i][i] := 0​
for L from 2 to n // chain length​
for i from 1 to n-L+1​
j := i + L - 1​
cost[i][j] := ∞​
for k from i to j-1​
q := cost[i][k] + cost[k+1][j] + p[i-1]*p[k]*p[j]​
if q < cost[i][j]​
cost[i][j] := q​
split[i][j] := k​

Example

Dimensions: ​
Chain:

Subchain Optimal Cost

(A1A2) 10×20×30 = 6000

(A2A3) 20×30×40 = 24000

(A3A4) 30×40×30 = 36000

(A1A2A3) min{(A1×A2)×A3, A1×(A2×A3)} =

min{6000+10×30×40, 24000+10×20×40} = 30000

(A2A3A4) min{24000+20×40×30, 36000+20×30×30} = 54000

(A1..A4) min{30000+10×40×30, 54000+10×20×30} =

30000+12000 = 42000
Traveling Salesperson Problem (TSP)

Find minimum-cost Hamiltonian cycle visiting all cities exactly once and returning to start.

DP with Bitmask

State : minimum cost to reach subset ending at city .

Recurrence

Pseudocode

for i from 0 to n-1​

DP[1<<i][i] := d[0][i] // start from city 0​
​
for S from 1 to (1<<n)-1​
if S contains 0​
for i in S, i ≠ 0​
DP[S][i] := ∞​
for j in S, j ≠ i​
DP[S][i] := min(DP[S][i], DP[S\{i}][j] + d[j][i])​
​
answer := ∞​
for i from 1 to n-1​
answer := min(answer, DP[(1<<n)-1][i] + d[i][0])​

Complexity

●​ Time:

●​ Space:

Summary of Algorithms
Problem Algorithm Time Complexity Space Complexity Key Feature

String Matching Naive O(mn) O(1) Simplicity

String Matching Rabin–Karp O(n + m) avg O(1) Rolling hash

String Matching KMP O(n + m) O(m) Prefix-suffix table

String Matching Boyer–Moore O(n/m) avg O(m + Σ ) H

e
u
r
i
s
t
i
c
s

Matrix Chain DP O(n³) O(n²) Optimal

parenthesization

TSP Bitmask DP O(n²2^n) O(n2^n) Exact exponential

DP

This collection demonstrates core algorithmic paradigms—brute force, hashing, dynamic

programming, greedy heuristics, and exponential DP—essential for efficient problem solving in
computer science.

NP-Hard and NP-Complete Problems,

Non-Deterministic and Randomized Algorithms
Basic Complexity Classes

●​ P: Decision problems solvable in polynomial time by a deterministic Turing machine.

●​ NP: Decision problems for which a given solution (certificate) can be verified in
polynomial time by a deterministic Turing machine.

●​ NP-Hard: Problems at least as hard as the hardest problems in NP. Formally, a problem 𝐻
is NP-Hard if for every 𝐿 ∈ 𝑁𝑃, 𝐿 is polynomial-time reducible to 𝐻.
 ●​ NP-Complete: Problems that are both in NP and NP-Hard.

Class Relationships

Class Definition Examples

P poly-time algorithm Sorting, MST, Shortest Path

(Dijkstra)

NP Poly-time verifiable SAT, Hamiltonian Cycle, Subset

Sum

NP-Hard At least as hard as NP Halting Problem (undecidable),

TSP optimization

NP-Complete In NP and NP-Hard 3-SAT, CLIQUE, Vertex Cover

Non-Deterministic Algorithms

●​ Non-Deterministic Turing Machine (NTM): In each step, can branch into multiple
computational paths.

●​ Acceptance Criterion: NTM accepts input if any computational path accepts.

●​ Time Complexity: For decision problems, NTM “solves” in if there is at least one

accepting path of length .

Equivalence

Pseudocode Sketch (NTM for SAT)

NTM-SAT(ϕ):​
for each clause C in ϕ​
nondeterministically choose a Boolean assignment for variables in C​
if all clauses satisfied​
accept​
else​
reject​
NP-Hard and NP-Complete Classes

Polynomial-Time Reduction

A language 𝐿1 reduces to 𝐿2 (𝐿1≤𝑝𝐿2) if a polynomial-time computable function 𝑓 maps inputs of

𝐿1 to inputs of 𝐿2 preserving membership:​

NP-Complete Definition

𝐿 ∈ 𝑁𝑃
′ ′
1.​ For every 𝐿 ∈ 𝑁𝑃, 𝐿 ≤𝑝𝐿

Examples of NP-Complete Problems

Problem Description Recurrence/Cost

3-SAT CNF satisfiability with 3 literals per NP-Complete

clause

CLIQUE Does graph contain clique of size 𝑘 NP-Complete

?

VERTEX COVER Does graph have vertex cover of NP-Complete

size 𝑘?

HAMILTONIAN CYCLE Cycle visiting each vertex exactly NP-Complete

once

Cook’s Theorem

●​ Statement: The Boolean satisfiability problem (SAT) is NP-Complete.

●​ Implications: Every problem in NP can be reduced in polynomial time to SAT.

Proof Sketch

1.​ Encode NTM computation tableau for input 𝑥 as Boolean variables.

2.​ Formulate constraints ensuring valid transitions and acceptance.

3.​ Construct CNF formula ϕ𝑥 satisfiable iff NTM accepts 𝑥.

 4.​ Reduction 𝑥↦ϕ𝑥 is polynomial-time computable.

Randomized Algorithms

●​ Las Vegas: Always correct; running time is a random variable.

●​ Monte Carlo: Running time is deterministic or bounded; answer may be incorrect with
small probability.

Randomized Complexity Classes

●​ RP: Problems where “yes” instances accepted with probability ≥ 1/2; “no” instances
always rejected.

●​ co-RP: “No” instances accepted with probability ≥ 1/2; “yes” instances always accepted.

●​ BPP: Both error probabilities ≤ 1/3 for “yes” and “no” instances.

Example: Rabin–Miller Primality Test (Monte Carlo)

Pseudocode

RabinMiller(n, k):​
if n < 2: return composite​
write n−1 as 2^s·d with d odd​
for i = 1 to k:​
a := random integer in [2, n−2]​
x := a^d mod n​
if x = 1 or x = n−1: continue next iteration​
for r = 1 to s−1:​
x := x^2 mod n​
if x = n−1: break​
if x ≠ n−1: return composite​
return probably prime​

●​ Time Complexity: with fast modular exponentiation.

●​ Error: False “probably prime” ≤ .

Example: Quick Sort (Randomized Pivot)

 ●​ Las Vegas: Randomly choose pivot to guarantee expected time.

Pseudocode

RandomizedQuickSort(A, lo, hi):​

if lo < hi:​
pivotIndex := random integer in [lo, hi]​
swap A[pivotIndex] with A[hi]​
p := Partition(A, lo, hi)​
RandomizedQuickSort(A, lo, p-1)​
RandomizedQuickSort(A, p+1, hi)​

Summary Table

Concept Key Idea Complexity Example

NP Polynomial-time – CLIQUE verification

verifiable

NP-Hard At least as hard as NP – TSP optimization

NP-Complete In NP and NP-Hard – 3-SAT

Cook’s Theorem SAT is NP-Complete – Reduction from NTM

Las Vegas Randomized time, exact Expected poly time Randomized Quick Sort
answer

Monte Carlo Fixed time, probabilistic Poly time Rabin–Miller test

correctness

This detailed overview covers formal definitions, reductions, central theorems, and exemplar
randomized algorithms with pseudocode, demonstrating foundational concepts in
computational complexity and algorithm design.

Parallel Algorithms and PRAM Model

Parallel Algorithm Analysis Models
Work and Span (Brent’s Theorem)

●​ Work : Total number of operations executed by the algorithm (sequential time ).

●​ Span : Length of the longest sequence of dependent operations (critical path length,
parallel time on infinite processors ).

Formulas:​

PRAM (Parallel Random Access Machine)

Abstract shared-memory model with processors, synchronous steps, unit-time memory

access.

Variant Read Write Conflict Resolution

EREW Exclusive Exclusive No concurrent access

CREW Concurrent Exclusive Reads allowed

concurrently

ERCW Exclusive Concurrent Writes allowed

concurrently without
conflict

CRCW Concurrent Concurrent Writes resolved by rule:

Common/Arbitrary/Priorit
y

Parallel Algorithm Structure

Typical phases in parallel algorithms:

1.​ Partition: Divide problem into subproblems.

2.​ Local Computation: Each processor works independently.

 3.​ Communication / Synchronization: Exchange data or synchronize at barriers.

4.​ Combine / Reduction: Merge partial results.

Example: Parallel Reduction (Sum)

Flowchart of a parallel reduction algorithm

Pseudocode (CREW PRAM)

function parallelSum(A[0..n-1], p):​

// Step 1: Partition​
chunkSize := ceil(n/p)​
parallel for i in 0..p-1:​
localSum[i] := 0​
for j in i*chunkSize to min((i+1)*chunkSize-1, n-1):​
localSum[i] := localSum[i] + A[j]​
barrier() // synchronization​
​
// Step 2: Tree-based reduction​
stride := 1​
 while stride < p do​
parallel for i in 0..p-1 by 2*stride:​
if i+stride < p:​
localSum[i] := localSum[i] + localSum[i+stride]​
stride := 2*stride​
barrier()​
return localSum[0]​

Complexity

●​ Work:

●​ Span:

●​ Speedup:

Example: Parallel Prefix (Scan)

Recurrence

For array , compute prefix sums .

Up-Sweep Phase (reduce)

for d in 0 to log2(n)-1:​
parallel for k in 0 to n-1 by 2^{d+1}:​
A[k + 2^{d+1} - 1] := A[k + 2^d - 1] + A[k + 2^{d+1} - 1]​

Down-Sweep Phase (distribute)

A[n-1] := 0​
for d in log2(n)-1 down to 0:​
parallel for k in 0 to n-1 by 2^{d+1}:​
t := A[k + 2^d - 1]​
A[k + 2^d - 1] := A[k + 2^{d+1} - 1]​
 A[k + 2^{d+1} - 1] := t + A[k + 2^{d+1} - 1]​

Complexity

●​ Work:

●​ Span:

●​ Efficiency:

PRAM Algorithms Example: Parallel Merge Sort

Step Work Span

Divide — 𝑂(1)

Recursive Sort 2𝑇(𝑛/2) 𝑇∞(𝑛/2)

Parallel Merge Θ(𝑛) 𝑂(𝑙𝑜𝑔⁡𝑛)

Recurrence 𝑇(𝑛) = 2𝑇(𝑛/2) + Θ(𝑛) 𝑇∞(𝑛) = 𝑇∞(𝑛/2) + 𝑂(𝑙𝑜𝑔⁡𝑛)

Solution Work: Θ(𝑛𝑙𝑜𝑔⁡𝑛)

2
Span: Θ(𝑙𝑜𝑔 ⁡𝑛)

Conclusion

Parallel algorithm design uses the PRAM model, analysis via work/span, and structured
phases—partition, local compute, synchronization, and combination—to achieve scalable
performance. Understanding PRAM variants and performance bounds is essential for efficient
parallel implementations.

Parallel Algorithms for Sorting, Searching, and

Merging
Complexity Metrics

●​ Work 𝑊: Total operations

 ●​ Span 𝑆: Critical-path length

●​ Parallel time on 𝑝 processors:​

Parallel Sorting Algorithms

1. Parallel Merge Sort (PRAM)

●​ Approach: Divide array, sort halves in parallel, then parallel merge.

Recurrence

Work:​

​
Span:​

Pseudocode (CREW PRAM)

parallelMergeSort(A, n):​
if n ≤ 1: return​
parallel:​
parallelMergeSort(A[0..n/2-1], n/2)​
parallelMergeSort(A[n/2..n-1], n-n/2)​
barrier()​
parallelMerge(A, 0, n/2, n)​

Parallel Merge

parallelMerge(A, low, mid, high):​

// Each processor merges a chunk​
p := number of processors​
for i in parallel 0..p-1:​
// compute rank ranges by binary search​
start1 := rank(i*(mid-low)/p, A[low..mid-1], A[mid..high-1])​
start2 := rank(i*(mid-low)/p, A[mid..high-1], A[low..mid-1])​
merge sequentially A[low+start1 .. mid-1] and A[mid+start2 .. high-1] into B​
 copy B back to A[low..high-1]​

●​ Work:

●​ Span:

2. Bitonic Sort (Sorting Network)

●​ Approach: Construct bitonic sequences and merge them.

Recurrence

​
(using 𝑛 processors)

Pseudocode

bitonicSort(A, lo, n, dir):​

if n > 1:​
k := n/2​
parallel:​
bitonicSort(A, lo, k, 1) // ascending​
bitonicSort(A, lo+k, k, 0) // descending​
barrier()​
bitonicMerge(A, lo, n, dir)​
​
bitonicMerge(A, lo, n, dir):​
if n > 1:​
m := greatest power of 2 < n​
parallel for i from lo to lo+n-m-1:​
if (A[i] > A[i+m]) == dir​
swap A[i], A[i+m]​
barrier()​
bitonicMerge(A, lo, m, dir)​
bitonicMerge(A, lo+m, n-m, dir)​

●​ Work:

●​ Span:
3. Odd–Even Transposition Sort

●​ Approach: Repeated parallel compare-and-swap on adjacent pairs.

Pseudocode

oddEvenSort(A, n):​
for phase from 1 to n:​
if phase is odd:​
parallel for i in 1,3,5,…<n:​
if A[i] > A[i+1]: swap​
else:​
parallel for i in 0,2,4,…<n-1:​
if A[i] > A[i+1]: swap​

●​ Work:

●​ Span:

Parallel Searching

1. Parallel Binary Search

●​ Approach: Search multiple keys simultaneously or search one key by dividing processors
to compare at different positions.

Pseudocode (search single key 𝑘 in sorted 𝐴[0.. 𝑛 − 1])

parallelBinarySearch(A, n, k):​
lo := 0; hi := n​
while hi - lo > p: // until range small​
parallel for i in 0..p-1:​
idx[i] := lo + i*(hi-lo)/p​
comp[i] := compare(A[idx[i]], k)​
barrier()​
// find processor j where comp[j] changes from <0 to ≥0​
j := index of first comp[i] ≥ 0​
hi := idx[j]; lo := idx[j-1]​
// fallback sequential binary search on A[lo..hi]​
 ●​ Span:

●​ Work:

2. Parallel Multi-Search

●​ Given 𝑚 queries and sorted 𝐴, distribute queries among processors and perform
independent binary searches in parallel.

●​ Time: per query (fully parallel)

Parallel Merging

Parallel Two-Way Merge

●​ Approach: Divide merge result into 𝑝 segments via binary searches.

Pseudocode

parallelMerge(A, B, C, n, m, p):​
// A[0..n-1], B[0..m-1], output C[0..n+m-1]​
for t in parallel 0..p-1:​
// rank positions​
i := rank(t*(n+m)/p, A, B)​
j := t*(n+m)/p - i​
u := rank((t+1)*(n+m)/p, A, B)​
v := (t+1)*(n+m)/p - u​
merge sequentially A[i..u-1] and B[j..v-1] into C[t*(n+m)/p .. (t+1)*(n+m)/p -1]​

●​ Work:

●​ Span:

Performance Summary

Algorithm Work Span Key Parameter

Parallel Merge Sort Θ(𝑛𝑙𝑜𝑔⁡𝑛) 2

Θ(𝑙𝑜𝑔 ⁡𝑛) PRAM processors

Bitonic Sort 2 2
Θ(𝑙𝑜𝑔 ⁡𝑛) Sorting network stages
Θ(𝑛𝑙𝑜𝑔 ⁡𝑛)
Odd–Even Transposition 2 Θ(𝑛) Phases = n
Θ(𝑛 )
Sort

Parallel Binary Search Θ(𝑙𝑜𝑔⁡𝑛) 𝑂(𝑙𝑜𝑔𝑝⁡𝑛 + 𝑙𝑜𝑔⁡(𝑛/𝑝)) Processors for search

Parallel Multi-Search Θ(𝑚𝑙𝑜𝑔⁡𝑛) Θ(𝑙𝑜𝑔⁡𝑛) 𝑚 parallel queries

Parallel Two-Way Merge Θ(𝑛 + 𝑚) 𝑂(𝑙𝑜𝑔⁡(𝑛 + 𝑚) +

𝑛+𝑚
) Segmentation by p
𝑝