Chapter 1: Algorithm Analysis - I

Reference: "AlgorithmAnalysis -1 (1).pdf"

This chapter introduces the fundamental concepts of judging the efficiency and speed of an algorithm
independently of its implementation, utilizing Order Analysis and Big-O Notation.

1. Big-O Notation and Growth Rates

The goal is to provide qualitative insight into the number of operations required for a problem of size n.
The term that dominates as n grows determines the order, allowing us to ignore constants and lower-
order terms.

Formal Definition: A function f(n) is O(g(n)) if there exist positive constants c and N such that f(n) ≤ c ×
g(n) for all n ≥ N.

Step-by-Step Example: Finding Big-O Constants

Problem: Prove that f(n) = 4n2 + 3n + 10 is O(n2).

1. Set up the inequality: Find c such that 4n2 + 3n + 10 ≤ c × n2.

2. Make an initial guess for c: The coefficient of the dominant term is 4. Let's try c = 5.

3. Test values of n:
◦ If n = 1: 4(1) + 3(1) + 10 = 17. Is 17 ≤ 5(1)? No.

◦ If n = 4: 4(16) + 3(4) + 10 = 86. Is 86 ≤ 5(16) = 80? No.

◦ If n = 5: 4(25) + 3(5) + 10 = 125. Is 125 ≤ 5(25) = 125? Yes!

4. Conclusion: The condition holds true for c = 5 and N = 5. Thus, it is O(n2).

2. Analyzing Code Complexity

To analyze code, determine the total number of repetitive operations (like mathematical operations inside
loops).
Step-by-Step Example: Nested Loops

Code Fragment:

for (i = 1; i ≤ n; i++) {
for (j = 1; j ≤ n; j++) {
x++;
}
}

1. Identify the outer loop: It runs n times.

2. Identify the inner loop: For each iteration of the outer loop, the inner loop runs n times.

3. Calculate total operations: Multiply the executions since they are nested. Total operations = n ×

n = n 2.

4. Result: Time complexity is O(n2).

1. Asymptotic Notations

• Big-O (O): Represents the Upper Bound (Worst-case scenario).

• Omega (Ω): Represents the Lower Bound (Best-case scenario).

• Theta (Θ): Represents Exact Asymptotic Behavior (Average-case / tight bound).

2. Solving Recurrences

Recursive algorithm times can be expressed mathematically as recurrence relations. Methods to solve
them include the Substitution Method, Recursion Tree Method, and Master Theorem.

Step-by-Step Example: Recursion Tree Method

Problem: Solve T(n) = 2T(n/2) + n

1. Draw the tree: Root is n. It splits into two children of size n/2. They split into four of size n/4,
etc.

2. Cost per level:

◦ Level 1: n/2 + n/2 = n

◦ Level 2: 4 × (n/4) = n

3. Determine depth: The problem size reduces by half each time until it hits 1. Depth is log n.
2
4. Total Cost: Summing the costs of all levels gives n × log n. Result: Θ(n log n).
2

Step-by-Step Example: The Master Theorem

For recurrences of form: T(n) = aT(n/b) + f(n), compare f(n) with nlogba.

1. Case 1: If f(n) grows slower, T(n) = Θ(nlogba).

2. Case 2: If f(n) grows at the same rate, T(n) = Θ(nlogba log n).

3. Case 3: If f(n) grows faster, T(n) = Θ(f(n)).

1. Merge Sort

A stable sort that guarantees O(n log n) runtime by dividing the array into two halves, recursively sorting
each, and merging them.

Step-by-Step Example: Merge Function

Goal: Merge sorted lists X=[3, 10, 23] and Y=[1, 5, 25]

1. Start pointers at the beginning of X and Y. Compare X[0]=3 and Y[0]=1.

2. 1 is smaller. Place 1 in the result. Advance Y pointer.

3. Compare X[0]=3 and Y[1]=5. 3 is smaller. Place 3 in result. Advance X pointer.

4. Continue until one list is exhausted. Result: [1, 3, 5, 10, 23, 25].

2. Quick Sort

Generally the fastest in practice. It averages O(n log n) but degrades to O(n2) if the pivot is chosen poorly
(e.g., already sorted array). It operates in-place.

Step-by-Step Example: In-Place Partitioning

Array: [5, 3, 6, 9, 2, 4, 7, 8]. Pivot: 5.

1. Start left counter at index 1 and right counter at the end.

2. Advance left until an element ≥ 5 is found (stops at 6).

3. Advance right backwards until an element < 5 is found (stops at 4).

4. Swap them: Array becomes [5, 3, 4, 9, 2, 6, 7, 8].

5. Continue: Left stops at 9, right stops at 2. Swap them: [5, 3, 4, 2, 9, 6, 7, 8].

6. Continue: Left stops at 9, right stops at 2. The pointers have crossed!

7. Swap the pivot (5) with the element at the right pointer (2): [2, 3, 4, 5, 9, 6, 7, 8]. The pivot 5 is
now in its final sorted position.
Chapter 4: Greedy Algorithms

Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most
obvious and immediate benefit (local optimum) in the hopes of reaching the global optimum.

1. Fractional Knapsack Problem

Step-by-Step Example: Fractional Knapsack

Problem: Capacity W = 60. Items: A(w:5, v:30), B(w:10, v:40), C(w:15, v:45), D(w:22, v:77), E(w:
25, v:90).

1. Compute ratios (Value/Weight): A=6, B=4, C=3, D=3.5, E=3.6.

2. Sort descending by ratio: A, B, E, D, C.

3. Take full amounts:

◦ Take B: Weight remaining = 45. Value = 70.

◦ Take E: Weight remaining = 20. Value = 160.

4. Take fraction: Next is D (w:22). We only have 20 capacity left. Take fraction 20/22 of D. Value
added = (20/22) × 77 = 70.

5. Total Value: 160 + 70 = 230.

2. Job Sequencing with Deadlines

Step-by-Step Example: Job Sequencing

1. Sort all jobs in decreasing order of profit.

2. Find the maximum available time slot for the current job (from deadline down to 1).

3. If a slot is empty, assign the job. If all slots prior to deadline are full, reject the job.
Chapter 5: Graphs - Minimum Spanning Trees

A spanning tree connects all nodes in a graph without cycles. A Minimum Spanning Tree (MST)
minimizes total edge weight.

1. Kruskal's Algorithm

Step-by-Step Procedure: Kruskal's

1. Sort all edges in the graph in ascending order of their weights.

2. Initialize a forest where each node is its own tree.

3. Iterate through the sorted edges: Pick the cheapest edge.

4. If the edge connects two different trees (does not form a cycle), add it to the MST.

5. Stop when the MST contains V - 1 edges. (Time complexity: O(E log E)).

2. Prim's Algorithm

Step-by-Step Procedure: Prim's

1. Start with an arbitrary node and add it to the MST.

2. Look at all edges that connect a node inside the MST to a node outside the MST.

3. Select the edge with the minimum weight and add the new node to the MST.

4. Repeat until all nodes are included. (Time complexity: O(E log V)).
Chapter 6: String Matching

String matching involves finding a pattern P within a text T. Applications include text editors and web
search engines.

1. Naive String Matching

Tests all possible placements of the pattern relative to the text. In the worst case, this algorithm runs in
O((n-m+1)m) which simplifies to O(nm).

2. Longest Common Subsequence (LCS) - Dynamic Programming

Finds the longest subsequence present in both strings. This has optimal substructure and overlapping
subproblems.

Step-by-Step Algorithm: LCS using DP

Goal: Find LCS of X and Y of lengths m and n.

1. Create a table C of size (m+1) × (n+1).

2. Initialize row 0 and column 0 with zeros.

3. For each character i in X and j in Y:

◦ If X[i] ≠ Y[j], set C[i,j] = max(C[i-1, j], C[i, j-1]). Draw an arrow pointing to the cell with the
larger value (Up or Left).

4. Traceback: Start at C[m,n]. Follow the arrows. Whenever you follow a diagonal arrow, append
that character to the LCS and reverse the final string. Time complexity is O(mn).