Algorithms

NPTEL / GATE CS / UGC NET Foundation Module Exam Weightage: 2–3 Direct Questions on Master Theorem cases, comparing growth rates of functions, and recursion trees.

1. Prerequisites & What You Should Know#

Before studying asymptotic analysis, ensure you understand:

• Basic Mathematics: Logarithms ($\log_2 n$), exponents, summations ($\sum$), and limits.
• Loops & Recursion: How to count the number of operations a loop or recursive call executes.
• Functions: What a mathematical function is — input goes in, output comes out.

2. What is Asymptotic Analysis? (Conceptual Explanation)#

2.1 The "How Fast Does It Grow?" Question#

When you write an algorithm, you need to ask: "As my input grows larger and larger, how does the time (or memory) my algorithm uses grow?"

Think of it like comparing commute speeds:

• Walking: Time grows linearly with distance — 2× distance = 2× time.
• Driving: Time grows more slowly (highways) — 2× distance ≠ 2× time.
• Teleporting: Time is constant — 1 mile or 1000 miles, same time.

Asymptotic analysis measures the growth rate of algorithms, not the exact time.

2.2 Why Not Just Time It with a Stopwatch?#

Asymptotic analysis is hardware-independent, language-independent, and focuses on the fundamental growth rate!

2.3 Counting Operations: The Key Idea#

// How many times does the innermost operation execute?

// Example 1: O(n) — Linear
for (int i = 0; i < n; i++) {    ← loop runs n times
    sum += arr[i];                ← 1 operation per iteration
}
// Total: n operations → O(n)

// Example 2: O(n²) — Quadratic
for (int i = 0; i < n; i++) {        ← outer runs n times
    for (int j = 0; j < n; j++) {    ← inner runs n times FOR EACH i
        count++;                      ← 1 operation
    }
}
// Total: n × n = n² operations → O(n²)

// Example 3: O(log n) — Logarithmic
while (n > 1) {      ← how many times can you halve n?
    n = n / 2;        ← halving each time
}
// n → n/2 → n/4 → ... → 1 takes log₂(n) steps → O(log n)

2.4 While Loop Condition Testing vs. Body Execution (NPTEL Week 1 Quiz & GATE Trap)#

A classic conceptual pitfall in algorithmic analysis (frequently tested in NPTEL Week 1 Quizzes and GATE CS) is the subtle distinction between:

1. How many times the loop body executes (the statements inside { ... })
2. How many times the loop condition is tested / evaluated (the boolean expression in while (...))

The Fundamental Rule of Loop Condition Testing#

For any standard pre-tested loop (while (condition) or for (; condition; )), the condition must be evaluated one extra time beyond the iterations that succeed, in order to evaluate to false and terminate the loop:

$ext{Total Condition Evaluations} = ( ext{Number of Successful Iterations}) + 1$

Case Study: NPTEL Week 1 Quiz Problem#

Consider the following function called with arguments $m = 165$ and $n = 15$:

def f(m, n):
    ans = 1
    while m >= 0:
        ans = ans * (ans + 1)
        m = m - n
    return ans

Problem: How many times is the while condition tested if $f(165, 15)$ is called?

Step-by-Step Execution Trace Table#

Mathematical Derivation#

1. The sequence of values tested for $m$ forms an Arithmetic Progression (AP): $m_k = 165 - 15k, \quad \text{for } k = 0, 1, 2, \dots$
2. The loop condition is $m_k \ge 0$: $165 - 15k \ge 0 \implies 15k \le 165 \implies k \le 11$
3. Since $k$ starts at $0$ and goes up to $11$, there are $11 - 0 + 1 = 12$ iterations where the condition is True (the loop body executes 12 times).
4. For $k = 12$, $m_{12} = 165 - 15(12) = -15$. The condition $-15 \ge 0$ is tested a 13th time and returns False.
5. Final Answer: The condition is tested $12 + 1 = 13$ times!

2.5 Loop Invariants: Program State & Correctness Analysis (NPTEL Week 1 Quiz Q5)#

A Loop Invariant is a formal condition or mathematical relation about program variables that is guaranteed to remain True before and after each iteration:

1. Initialization: True prior to the first iteration.
2. Maintenance: If True before iteration $k$, it remains True before iteration $k+1$.
3. Termination: When the loop terminates, the invariant holds and provides a guarantee about the final computed output.

Case Study: NPTEL Loop Invariant Question#

Consider the following program tracking integers partitioned into prime vs. composite accumulators:

i = 0; j = 0; k = 0;
for (m = last; m >= first; m = m - 1) {
    k = k - m;
    if (composite(m)) {
        i = i - m;
    } else {
        j = j - m;
    }
}

Question: Which condition (...) can replace if (...) at the end to guarantee it prints "True"?

Invariant Proof#

• Before Loop: $i = 0, j = 0, k = 0 \implies k = i + j = 0$ holds.
• In Each Iteration:
  • $k$ changes by $\Delta k = -m$.
  • Exactly one branch executes:
    • If composite(m) is True: $\Delta i = -m$, $\Delta j = 0 \implies \Delta(i + j) = -m + 0 = -m = \Delta k$.
    • If composite(m) is False: $\Delta i = 0$, $\Delta j = -m \implies \Delta(i + j) = 0 - m = -m = \Delta k$.
• At Loop Termination: Since $\Delta k = \Delta(i + j)$ on every single step regardless of $m$, the equality k == i + j is a universal loop invariant that holds for ANY values of first and last!

3. Asymptotic Notations: Mathematical Definitions#

3.1 Big-O Notation (Asymptotic Upper Bound)#

$f(n) = O(g(n)) \iff \exists \, c > 0, n_0 > 0 \text{ such that } 0 \le f(n) \le c \cdot g(n) \quad \forall \, n \ge n_0$ Meaning: $f(n)$ grows at most as fast as $g(n)$ (Worst-Case rate).

3.2 Big-$\Omega$ Notation (Asymptotic Lower Bound)#

$f(n) = \Omega(g(n)) \iff \exists \, c > 0, n_0 > 0 \text{ such that } 0 \le c \cdot g(n) \le f(n) \quad \forall \, n \ge n_0$ Meaning: $f(n)$ grows at least as fast as $g(n)$ (Best-Case rate).

3.3 Big-$\Theta$ Notation (Asymptotically Tight Bound)#

$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))$

3.4 Strict Bounds: Little-o and Little-$\omega$#

• $f(n) = o(g(n))$: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$ (Strictly slower growth).
• $f(n) = \omega(g(n))$: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$ (Strictly faster growth).

3.5 Quick Analogy#

4. Master Theorem for Divide-and-Conquer Recurrences#

For recurrences of the form: $T(n) = a \, T\left(\frac{n}{b}\right) + f(n) = a \, T\left(\frac{n}{b}\right) + \Theta(n^k \log^p n)$ where $a \ge 1$, $b > 1$, $k \ge 0$, and $p$ is a real number:

Master Theorem: Step-by-Step Example#

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

Step 1: Identify a=4, b=2, f(n)=n, so k=1, p=0
Step 2: Compute log_b(a) = log_2(4) = 2
Step 3: Compare log_b(a) with k:  2 > 1 → Case 1!
Step 4: Solution: T(n) = Θ(n^(log_2 4)) = Θ(n²)

Another: T(n) = 2T(n/2) + n
  a=2, b=2, k=1, log_2(2)=1, 1==1, p=0>-1 → Case 2a
  T(n) = Θ(n¹ · log^(0+1) n) = Θ(n log n) ← This is Merge Sort!

5. Hierarchy of Growth Rates#

$O(1) < O(\log \log n) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

For n = 1,000,000 (one million):

O(1)        → 1 operation              (instant)
O(log n)    → ~20 operations           (instant)
O(n)        → 1,000,000 operations     (~1 ms)
O(n log n)  → ~20,000,000 operations   (~20 ms)
O(n²)       → 1,000,000,000,000 ops    (~16 minutes!)
O(2^n)      → 2^1000000 operations     (longer than universe age)

5.1 Estimating Wall-Clock Runtime on Modern CPUs (NPTEL Week 1 Quiz Q3)#

Modern CPUs execute roughly $10^9$ basic operations per second ($1\text{ GHz}$ baseline):

$\text{Estimated Time (seconds)} = \frac{\text{Total Operations } T(n)}{\text{Processor Operations/sec}}$

Worked Example: $O(n^3)$ with $n = 30,000$#

• Total Operations: $T(n) = n^3 = (30,000)^3 = (3 \times 10^4)^3 = 27 \times 10^{12}$ operations.
• CPU Speed: $10^9$ ops/sec.
• Execution Time: $\text{Time} = \frac{27 \times 10^{12}}{10^9} = 27,000\text{ seconds}$ $\text{In Minutes:} \quad \frac{27,000}{60} = 450\text{ minutes}$ $\text{In Hours:} \quad \frac{450}{60} = 7.5\text{ hours}$
• Conclusion: $7.5\text{ hours}$ is strictly Under 8 hours (eliminating options Under 8 minutes, while Under 8 hours is the tightest valid bound).

5.2 Comparing Growth Rates & Upper Bounds for Fractional Powers (NPTEL Week 1 Quiz Q4)#

Consider $f(n) = n\sqrt{n} = n^{1.5}$:

• Versus $n \log n$: $\lim_{n \to \infty} \frac{n^{1.5}}{n \log n} = \lim_{n \to \infty} \frac{\sqrt{n}}{\log n} = \infty$. Thus $n\sqrt{n}$ grows strictly faster than $n \log n$, so $f(n) \ne O(n \log n)$ (Statement A is False).
• Versus $n^2$: $n^{1.5} \le n^2$ for $n \ge 1$. Hence $f(n) = O(n^2)$ is True (Statement B is True).
• Versus $n^4$: $n^{1.5} \le n^4$ for $n \ge 1$. Because Big-O is an upper bound, $f(n) = O(n^4)$ is also True (Statement C is True).
• Takeaway: (B) and (C) are true, but (A) is false!

6. Implementation in C, C++, and Python with Syntax Logic#

#include <stdio.h>
#include <time.h>

/**
 * C Syntax Logic Note:
 * 1. clock_t & clock(): Provided by <time.h> to measure processor execution time.
 * 2. CLOCKS_PER_SEC: Macro defining processor clock ticks per second (typically 1,000,000).
 * 3. Double casting: (double)(end - start) / CLOCKS_PER_SEC converts CPU ticks into seconds.
 */

// O(log n): Recursive division
int binarySearchSteps(int n) {
    if (n <= 1) return 1;
    return 1 + binarySearchSteps(n / 2); // Recurrence: T(n) = T(n/2) + O(1)
}

// O(n^2): Nested loops
long long quadraticWork(int n) {
    long long count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

void benchmark(int n) {
    clock_t start = clock();
    long long ops = quadraticWork(n);
    clock_t end = clock();

    double cpu_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("N = %d -> Operations = %lld, Elapsed = %f seconds\n", n, ops, cpu_time);
}

7. GATE, UGC NET & NPTEL Key Exam Insights#