Algorithm Analysis: Big-O, Complexity, Divide & Conquer, Greedy, Dynamic

TAKEAWAYS:

• Big-O notation describes algorithmic efficiency by focusing on growth rate (e.g., $O(n)$, $O(n^2)$, $O(\log n)$), ignoring constants and lower-order terms.
• Divide-and-conquer splits problems into smaller subproblems (e.g., merge sort, binary search), reducing complexity from $O(n^2)$ to $O(n\log n)$.
• Greedy algorithms make locally optimal choices (e.g., Dijkstra’s shortest path, Huffman coding) but may not always yield globally optimal solutions.
• Dynamic programming solves overlapping subproblems by storing intermediate results (e.g., Fibonacci sequence, knapsack problem) to avoid redundant calculations.
• Space-time tradeoffs exist: some algorithms use more memory (e.g., memoization) to save computation time.
• Amortized analysis explains why operations like append() in dynamic arrays appear $O(1)$ on average despite occasional $O(n)$ resizing.

1. Why Analyze Algorithms?

Algorithms are the backbone of software efficiency. Without analysis, we cannot predict:

• How long a program will run for large inputs (e.g., sorting 1 million records).
• How much memory it will consume (e.g., storing a graph with 10,000 nodes).
• Whether it will scale for real-world use (e.g., handling 1000+ concurrent users in an app).

Example: A linear search ($O(n)$) takes 1 second for 100 items. For 1 million items, it would take 10,000 seconds (~2.7 hours). A binary search ($O(\log n)$) would take only 20 seconds for the same dataset.

2. Big-O Notation: The Language of Efficiency

Big-O describes the upper bound of an algorithm’s growth rate as input size $n$ increases. It ignores:

• Constants (e.g., $2n$ → $O(n)$).
• Lower-order terms (e.g., $n^2+n$ → $O(n^2)$).

Common Complexity Classes

Visual: Growth Rates

Key Rules:

1. Worst-case analysis: Big-O describes the slowest possible scenario.
2. Asymptotic behavior: Focus on behavior as $n\to \infty$.
3. Not exact runtime: It does not give seconds or milliseconds.

Example: For the algorithm:

def sum_array(arr):
    total = 0
    for num in arr:       # O(n)
        total += num
    for num in arr:       # O(n)
        total += num
    return total           # O(1)

The total complexity is $O(n)+O(n)=O(2n)=O(n)$.

3. In the Real World

Example 1: eSewa and Khalti (Payment Processing)

• Idea Used: Greedy Algorithm for Transaction Routing
  • When you pay via eSewa/Khalti, the app must quickly route your transaction to the nearest bank or payment gateway.
  • A greedy approach selects the closest available server (lowest latency) without reconsidering past choices, ensuring near-instant processing.
  • Why it matters: If Khalti used a brute-force method ($O(n!)$), processing 1000 transactions would take years.

Example 2: Daraz (Order Fulfillment Queue)

• Idea Used: Priority Queue (Greedy + Divide-and-Conquer)
  • Daraz prioritizes orders based on urgency (e.g., "Same-day delivery") and distance from warehouse.
  • A min-heap (priority queue) ensures the most urgent order is processed first ($O(\log n)$ insertion).
  • Real-world impact: Without this, a customer ordering at 11:59 PM might get their package after someone who ordered at 12:01 AM.

Example 3: NTC (Network Routing with Dijkstra’s Algorithm)

• Idea Used: Shortest Path (Greedy + Dynamic Programming)
  • The Nepal Telecommunications Company (NTC) uses Dijkstra’s algorithm to route internet traffic through the least congested paths.
  • How it works:
    1. Start from the source node (e.g., Kathmandu).
    2. Greedily pick the cheapest path to each neighbor.
    3. Update distances dynamically as new data arrives.
  • Result: Faster internet speeds and reduced costs.

Example 4: NEPSE (Stock Market Matching)

• Idea Used: Divide-and-Conquer for Order Matching
  • When you buy/sell stocks on NEPSE, the system must match buy/sell orders in milliseconds.
  • A divide-and-conquer approach splits orders into price buckets (e.g., ₹100–₹110) and matches them locally before merging results.
  • Why it’s critical: A delay of even 1 second could cost traders millions.

Example 5: Pathao (Ride Matching with Hashing)

• Idea Used: Hash Tables for Rider-Driver Matching
  • Pathao uses geohashing to group riders/drivers by location (e.g., "Kathmandu-3" → all users near Thapathali).
  • When you request a ride, Pathao hashes your location to find the nearest driver in $O(1)$ time.
  • Without hashing: A linear search ($O(n)$) would make ride requests take minutes instead of seconds.

4. Divide-and-Conquer: Breaking Problems into Smaller Pieces

Definition: An algorithm that:

1. Divides a problem into smaller subproblems of the same type.
2. Conquers each subproblem recursively.
3. Combines the results to solve the original problem.

Merge sort: Divide, conquer, and combine phases (Image: VineetKumar at English Wikipedia, Public domain, via Wikimedia Commons)

Key Examples:

1. Binary Search ($O(\log n)$)
   • Divides a sorted array into halves until the target is found.
2. Merge Sort ($O(n\log n)$)
   • Splits the array, sorts subarrays, and merges them.
3. Strassen’s Matrix Multiplication
   • Reduces matrix multiplication from $O(n^3)$ to $O(n^{2.81})$.

Algorithm: Binary Search

flowchart TD
    A["Start"] --> B["Set low=0, high=n-1"]
    B --> C{"Is low <= high?"}
    C -->|"Yes"| D["mid = (low + high)/2"]
    D --> E{"Is arr[mid] == target?"}
    E -->|"Yes"| F["Return mid"]
    E -->|"No"| G{"Is arr[mid] < target?"}
    G -->|"Yes"| H["low = mid + 1<br/>Go to C"]
    G -->|"No"| I["high = mid - 1<br/>Go to C"]
    C -->|"No"| J["Return -1 (Not found)"]

Code Implementation:

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

Trace for arr = [1, 3, 5, 7, 9], target = 5:

Real-World Trace: NTC Internet Routing Suppose NTC has a sorted list of ISPs by latency (in ms): [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] You want the fastest ISP under 40 ms.

• Step 1: low=0, high=9, mid=4 → arr[4]=50 (too high) → high=3.
• Step 2: mid=1 → arr[1]=20 (valid) → select ISP 20 ms.

5. Greedy Algorithms: Making the Best Local Choice

Definition: An algorithm that makes the locally optimal choice at each step, hoping it leads to a globally optimal solution.

When to Use:

• Problems with optimal substructure (e.g., shortest path, Huffman coding).
• No need to reconsider past choices (e.g., coin change with fixed denominations).

When It Fails:

• If local choices conflict with global goals (e.g., activity selection with overlaps).

Example 1: Dijkstra’s Shortest Path (NTC Network Routing)

Problem: Find the shortest path from Kathmandu to Pokhara with the following graph (weights = latency in ms):

Algorithm Steps:

1. Start at Kathmandu (dist[K] = 0).
2. Pick the nearest unvisited node (greedy choice).
3. Update distances to neighbors.

Trace:

Final Path: Kathmandu → Bhaktapur → Nepalgunj → Pokhara (45 ms).

Why Greedy Works Here:

• Each step picks the closest unvisited node, ensuring no shorter path exists.

Example 2: Huffman Coding (Data Compression in Apps)

Problem: Compress text by assigning shorter codes to frequent characters.

Given Frequencies:

Steps:

1. Build a min-heap of frequencies.
2. Repeatedly combine the two least frequent nodes (greedy choice).
3. Assign codes based on the tree.

Trace:

Final Codes:

• E: 0 (most frequent)
• D: 10
• C: 110
• B: 1110
• A: 1111

Savings: Original text (50 chars) → 25 bits (ASCII) → 10 bits (Huffman).

Used in:

• WhatsApp (compressing messages).
• YouTube (reducing video file sizes).

6. Dynamic Programming: Storing Subproblems to Avoid Redundancy

Definition: A method to solve problems by:

1. Breaking them into overlapping subproblems.
2. Storing solutions to subproblems (memoization/table).
3. Combining results to get the final answer.

Key Differences from Divide-and-Conquer:

Example 1: Fibonacci Sequence

Problem: Compute the $n$-th Fibonacci number efficiently.

Naive Recursive Approach (Exponential Time $O(2^n)$):

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Trace for n=4:

fib(4) → fib(3) + fib(2)
       → (fib(2) + fib(1)) + (fib(1) + fib(0))
       → ( (fib(1) + fib(0)) + 1 ) + (1 + 0)
       → ( (1 + 0) + 1 ) + 1 = 3

Problem: Computes fib(2) and fib(1) multiple times!

Dynamic Programming Solution (Linear Time $O(n)$):

def fib_dp(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Trace for n=4:

Real-World Use: Stock Market Prediction (NEPSE)

• Predicting stock prices relies on historical patterns (overlapping subproblems).
• DP stores past price trends to avoid recalculating for each new data point.

Example 2: 0/1 Knapsack Problem

Problem: Given weights and values of items, maximize value in a knapsack of capacity $W$.

Input:

DP Table Approach:

def knapsack(W, wt, val, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

Trace for W=5:

Optimal Selection:

• Items A, B, D (total value = 3 + 4 + 6 = 13).

Used in:

• Daraz: Selecting the most valuable items to ship without exceeding weight limits.
• Pathao: Assigning drivers to maximize earnings while respecting time constraints.

7. Space-Time Tradeoffs

Sometimes, we trade memory for speed or vice versa.

Example: Factorial Calculation

# Recursive (O(n) space due to call stack)
def fact_rec(n):
    if n == 0: return 1
    return n * fact_rec(n-1)

# Iterative (O(1) space)
def fact_iter(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

8. Amortized Analysis: Average Case Over Many Operations

Some operations appear expensive occasionally but cheap on average.

Example: Dynamic Array (Python list)

• Append operation:
  • Usually $O(1)$ (just add to the end).
  • Occasionally $O(n)$ (when resizing is needed).
• Amortized cost: $O(1)$ per append.

Trace for 5 appends (capacity doubles at 3):

Total time: $3O(1)+1O(n)+1O(1)=O(n)$ for 5 operations → Amortized $O(1)$ per operation.

Used in:

• Khalti/eSewa: Handling sudden spikes in transactions without slowing down.

9. Exam Tip: How to Score Full Marks

Do’s:

✅ Always state the time/space complexity for every algorithm (e.g., "Binary search runs in $O(\log n)$ time"). ✅ Draw diagrams for divide-and-conquer (e.g., merge sort splits) and DP (e.g., knapsack table). ✅ Compare algorithms in a table (e.g., greedy vs. DP for shortest path). ✅ Trace step-by-step for small inputs (e.g., Fibonacci for $n=4$). ✅ Relate to real-world examples (e.g., "Like Daraz’s order prioritization").

Don’ts:

❌ Assume Big-O is exact runtime (e.g., "Binary search takes 0.001 seconds" → wrong). ❌ Skip edge cases (e.g., empty input, duplicate keys). ❌ Mix up greedy and DP (e.g., calling Dijkstra a DP algorithm → wrong). ❌ Ignore space complexity (e.g., only stating time but not memory usage).

Common Pitfalls in Exams:

1. Forgetting to sort first for binary search → must be sorted.
2. Using greedy for problems requiring DP (e.g., coin change with arbitrary denominations).
3. Not handling base cases in recursion → stack overflow.
4. Misapplying Big-O (e.g., $O(n^2+n)=O(n^2)$ is correct, but $O(n^2+1000n)=O(n)$ is wrong).

Model Answer Structure:

Question: "Explain Dijkstra’s algorithm with an example." Answer:

1. Definition: Greedy algorithm for shortest path in graphs with non-negative weights.
2. Steps:
   • Initialize distances (dist[src] = 0, others = ∞).
   • Use a priority queue to pick the nearest unvisited node.
   • Relax edges (update distances if a shorter path is found).
3. Example: (Draw the graph, show trace table as above).
4. Complexity: $O((V+E)\log V)$ with a binary heap.
5. Real-world use: NTC’s internet routing.

Final Tip:

• Practice tracing algorithms on paper (e.g., merge sort, Huffman coding).
• Memorize common complexities (e.g., binary search = $O(\log n)$).
• Relate to TU/PU exam patterns—often ask for pseudocode + trace + complexity.