Algorithms — Design, Analysis, and Techniques

Algorithm Basics and Complexity

An algorithm is a finite, well-defined sequence of steps to solve a problem.

Properties of Good Algorithm:

1. Finiteness — must terminate after finite steps
2. Definiteness — each step clearly defined
3. Input — zero or more inputs
4. Output — at least one output
5. Effectiveness — each step must be feasible

Asymptotic Notations:

| Notation | Meaning | Use | |---|---|---| | O (Big O) | Upper bound (worst case) | Most commonly used | | Ω (Omega) | Lower bound (best case) | Best case analysis | | Θ (Theta) | Tight bound (average case) | When best=worst |

Master Theorem for T(n) = aT(n/b) + f(n):

• If f(n) = O(n^(log_b a - ε)) → T(n) = Θ(n^log_b a)
• If f(n) = Θ(n^log_b a) → T(n) = Θ(n^log_b a · log n)
• If f(n) = Ω(n^(log_b a + ε)) → T(n) = Θ(f(n))

---

Sorting Algorithms

Bubble Sort

Compare adjacent elements and swap if out of order. Repeat n-1 passes.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

• Time: O(n²) worst/average, O(n) best (optimized with flag)
• Space: O(1) in-place
• Stable: Yes

Merge Sort (Divide and Conquer)

Split array in half, sort each half, merge sorted halves.

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

• Time: O(n log n) always
• Space: O(n) extra
• Stable: Yes
• Best for: Linked lists, external sorting

Quick Sort

Pick pivot, partition array, recursively sort partitions.

• Time: O(n log n) average, O(n²) worst
• Space: O(log n) stack space
• Stable: No (basic implementation)
• Best for: Arrays, cache-friendly

Heap Sort

Build max-heap, extract max repeatedly.

• Time: O(n log n) always
• Space: O(1)
• Stable: No

Sorting Algorithm Comparison:

| Algorithm | Best | Average | Worst | Space | Stable | |---|---|---|---|---|---| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | | 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 |

---

Searching Algorithms

Linear Search

Check each element one by one.

• Time: O(n) | Works on: Unsorted arrays

Binary Search

On sorted array: compare middle, eliminate half.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: low = mid + 1
        else: high = mid - 1
    return -1

• Time: O(log n) | Requires: Sorted array

---

Divide and Conquer

Strategy: Divide problem → Conquer subproblems → Combine results.

Examples:

• Merge Sort: T(n) = 2T(n/2) + O(n) → O(n log n)
• Quick Sort: T(n) = T(k) + T(n-k-1) + O(n)
• Binary Search: T(n) = T(n/2) + O(1) → O(log n)
• Strassen Matrix Multiplication: O(n^2.81) vs naive O(n³)

---

Dynamic Programming (DP)

DP solves problems with overlapping subproblems and optimal substructure by storing solutions.

Two Approaches:

1. Memoization (Top-Down): Recursion + cache
2. Tabulation (Bottom-Up): Iterative table-filling

Fibonacci — Classic DP Example

# Naive recursion: O(2ⁿ) — exponential!
# DP with memoization: O(n)
def fib(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

0/1 Knapsack Problem

Given weights and values of n items, maximize value in knapsack of capacity W.

dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])

• Time: O(n×W) | Space: O(n×W)

Longest Common Subsequence (LCS)

if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Important DP Problems:

• Coin Change (minimum coins)
• Longest Increasing Subsequence
• Matrix Chain Multiplication
• Edit Distance
• Rod Cutting

---

Greedy Algorithms

Make locally optimal choice at each step, hoping for global optimum.

Greedy works for: Activity selection, Huffman coding, Kruskal/Prim MST, Dijkstra.

Activity Selection Problem

Select maximum non-overlapping activities. Strategy: Always select activity with earliest finish time.

Huffman Coding

Variable-length encoding — frequent characters get shorter codes. Build tree: repeatedly merge two nodes with lowest frequency.

Greedy vs DP:

• Greedy: One choice at each step, doesn't reconsider — faster
• DP: Tries all options, stores results — more accurate but slower

---

Graph Algorithms

Dijkstra's Shortest Path

Single source shortest path for non-negative weights.

• Time: O((V+E) log V) with priority queue
• Cannot handle negative weights

Bellman-Ford

Handles negative weights. Detects negative cycles.

• Time: O(V×E)

Floyd-Warshall

All-pairs shortest path.

• Time: O(V³) | Space: O(V²)

Minimum Spanning Tree

Kruskal's Algorithm:

1. Sort all edges by weight
2. Add edge if it doesn't create cycle (use Union-Find)

• Time: O(E log E)

Prim's Algorithm:

1. Start from any vertex
2. Always add minimum weight edge connecting visited to unvisited

• Time: O((V+E) log V) with priority queue

---

Solved PYQ Questions

Q1 (2023): Apply merge sort on [38, 27, 43, 3, 9, 82, 10]

Split: [38,27,43] [3,9,82,10]
Split: [38][27,43] [3,9][82,10]
Split: [38][27][43] [3][9][82][10]
Merge: [27,38,43] [3,9,10,82]
Merge: [3,9,10,27,38,43,82] ✓

Q2 (2022): Find shortest path from A to all vertices using Dijkstra. Use priority queue, process minimum distance vertex first, relax all edges.

Q3 (2024): Solve 0/1 knapsack: items=(2,6),(2,10),(3,12), capacity=5

dp[3][5]:
Item 1 (w=2,v=6):  row 1: [0,0,6,6,6,6]
Item 2 (w=2,v=10): row 2: [0,0,10,10,16,16]
Item 3 (w=3,v=12): row 3: [0,0,10,12,16,22]
Maximum value = 22

---

Quick Revision Checklist

• Sorting: time/space complexity of all 7 algorithms
• Binary search: O(log n), requires sorted array
• Divide & Conquer: merge sort, binary search
• DP: memoization vs tabulation, knapsack, LCS
• Greedy: activity selection, Huffman coding
• Graph: Dijkstra, Bellman-Ford, Floyd-Warshall
• MST: Kruskal (sort edges) vs Prim (grow tree)
• Master theorem application