Section C: Step-by-Step Worked Example (The Application)

Question: Justify if $2n = o(n^2)$.

1. Apply the Limit Test: Set up the limit of $f(n) / g(n)$ as $n$ approaches infinity. $\lim_{n \to \infty} \frac{2n}{n^2}$
2. Simplify the expression: $= \lim_{n \to \infty} \frac{2}{n}$
3. Evaluate the limit: As $n$ grows infinitely large, any constant divided by infinity approaches zero. $= 0$
4. Conclusion: Since the limit is 0, $2n$ is indeed $o(n^2)$.

Section C: Step-by-Step Worked Example (The Application)

Example 1: Master’s Theorem Solve $T(n) = 3T(n/4) + n \log n$

1. Compare with the standard form: $T(n) = aT(n/b) + \Theta(n^k \log^p n)$
2. Extract the constants:
   • $a = 3$
   • $b = 4$
   • $f(n) = n \log^1 n \implies k = 1, p = 1$
3. Evaluate $b^k$:
   • $b^k = 4^1 = 4$
4. Compare $a$ and $b^k$:
   • $a = 3$ and $b^k = 4$.
   • Since $3 < 4$, we have $a < b^k$. This falls under Case 3.
5. Check $p$ for Case 3:
   • $p = 1$, which means $p \geq 0$.
6. Apply the formula: $T(n) = \Theta(n^k \log^p n)$
   • $T(n) = \Theta(n^1 \log^1 n)$
   • Final Answer: $T(n) = \Theta(n \log n)$

Example 2: Recursion Tree Method (April 2025 University Question) Solve $T(n) = 3T(n/4) + cn^2$

1. Level 0 (Root): The cost at the root is $cn^2$.
2. Level 1: The recurrence branches 3 ways ($a=3$). The input size drops to $n/4$.
   • Each node costs $c(n/4)^2 = cn^2 / 16$.
   • Total cost at Level 1 $= 3 \times (cn^2 / 16) = (3/16)cn^2$.
3. Level 2: Each of the 3 nodes branches 3 ways (9 nodes total). Input is $n/16$.
   • Each node costs $c(n/16)^2 = cn^2 / 256$.
   • Total cost at Level 2 $= 9 \times (cn^2 / 256) = (3/16)^2 cn^2$.
4. Level $i$ (General Case):
   • Number of nodes $= 3^i$.
   • Cost per node $= c(n/4^i)^2 = cn^2 / 16^i$.
   • Total cost at Level $i = (3/16)^i cn^2$.
5. Total Cost Summation:
   • $T(n) = \sum_{i=0}^{\log_4 n - 1} (3/16)^i cn^2 + \text{Leaf Cost}$
   • This is a geometric series with ratio $r = 3/16$.
   • $T(n) = cn^2 [1 + (3/16) + (3/16)^2 + \dots ]$
   • Using the infinite series formula $S = a / (1-r)$:
   • $T(n) < cn^2 \times \frac{1}{1 - 3/16} = cn^2 \times \frac{16}{13}$
6. Final Result:
   • $T(n) = O(n^2)$.

Example 3: Substitution Method (April 2025 University Question) Solve $T(n) = 2T(\lfloor n/2 \rfloor) + n$ where $T(1) = 1$.

1. Guess: Based on the form (similar to Merge Sort), we guess $T(n) = O(n \log n)$.
2. Inductive Goal: Prove $T(n) \leq cn \log n$ for some $c > 0$.
3. Inductive Step: Assume it holds for $n/2$, i.e., $T(n/2) \leq c(n/2) \log(n/2)$.
4. Substitute into Recurrence:
   • $T(n) \leq 2 [c(n/2) \log(n/2)] + n$
   • $T(n) \leq cn \log(n/2) + n$
   • $T(n) \leq cn (\log n - \log 2) + n$
   • $T(n) \leq cn \log n - cn + n$
5. Final Condition: We need $cn \log n - cn + n \leq cn \log n$.
   • This is true if $-cn + n \leq 0 \implies n(1-c) \leq 0$.
   • This holds for all $c \geq 1$.
6. Conclusion: $T(n) = O(n \log n)$.

Section C: Step-by-Step Worked Example (The Application)

Example 1: Prove that $f(n) = 2^{n+1}$ is $O(2^n)$ (April 2025 University Question)

1. State the definition: We need to find $c$ and $n_0$ such that $2^{n+1} \leq c \cdot 2^n$ for all $n \geq n_0$.
2. Algebraic Manipulation:
   • $2^{n+1} = 2^1 \cdot 2^n = 2 \cdot 2^n$
3. Identify the constants:
   • The inequality becomes $2 \cdot 2^n \leq c \cdot 2^n$.
   • This is true if we choose $c = 2$.
   • Since this holds for all $n \geq 1$, we set $n_0 = 1$.
4. Conclusion: Since there exist positive constants $c=2$ and $n_0=1$, $2^{n+1} = O(2^n)$.

Example 2: Is $2^{2n} = O(2^n)$? Justify your answer. (University Question)

1. State the definition: $2^{2n} \leq c \cdot 2^n$ for all $n \geq n_0$.
2. Algebraic Manipulation:
   • $(2^2)^n \leq c \cdot 2^n$
   • $4^n \leq c \cdot 2^n$
3. Analyze the ratio:
   • $4^n / 2^n \leq c$
   • $(4/2)^n \leq c$
   • $2^n \leq c$
4. Conclusion: There is no constant $c$ that can bound the function $2^n$ as $n$ approaches infinity. The ratio grows without bound.
5. Final Result: Therefore, $2^{2n} \neq O(2^n)$.

Example 3: Arrange functions by growth rate (University Question) $n^3, 2^n, \log n^3, 2^{100}, n^2 \log n, n^n, \log n, n^{0.3}, 2^{\log n}$

1. Constant: $2^{100}$
2. Logarithmic: $\log n$ and $\log n^3 = 3 \log n$
3. Fractional Power: $n^{0.3}$
4. Linear (via identity): $2^{\log_2 n} = n$
5. Linear-Logarithmic: $n^2 \log n$
6. Polynomial: $n^3$
7. Exponential: $2^n$
8. Factorial-like: $n^n$ Final Order: $2^{100} < \log n < \log n^3 < n^{0.3} < 2^{\log n} < n^2 \log n < n^3 < 2^n < n^n$.

Section C: Step-by-Step Worked Example (The Application)

Example 1: Analyze the time complexity of the following code segment

for(int i=1; i<=n; i++) {
    for(int j=1; j<=n; j++) {
        // O(1) statement
    }
}

1. Analyze Outer Loop: The outer loop i runs from $1$ to $n$. It successfully executes its body $n$ times.
2. Analyze Inner Loop: For every single iteration of the outer loop, the inner loop j resets and runs from $1$ to $n$, executing its body $n$ times.
3. Total Frequency Count: The innermost $O(1)$ statement executes $n$ (from outer) $\times$ $n$ (from inner) times.
4. Result: Total executions $= n^2$. Time Complexity $= O(n^2)$.

Example 2: Analyze an algorithmic segment with dependent bounds

for(int i=1; i<=n; i++) {
    for(int j=1; j<=i; j++) {
        // O(1) statement
    }
}

1. Trace iterations:
   • When $i = 1$, inner loop runs $1$ time.
   • When $i = 2$, inner loop runs $2$ times.
   • …
   • When $i = n$, inner loop runs $n$ times.
2. Sum the frequencies: Total executions $= 1 + 2 + 3 + \dots + n$
3. Apply Arithmetic Progression Formula: Sum of first $n$ natural numbers $= \frac{n(n+1)}{2} = \frac{n^2 + n}{2}$
4. Result: Dropping lower-order terms and constants, the Time Complexity $= O(n^2)$.

Example 3: Determine Space Complexity for a Recursive Array Sum

int RSum(int a[], int n) {
    if (n <= 0) return 0;
    return a[n] + RSum(a, n-1);
}

1. Fixed Space: Negligible (pointers and $n$ passed by value).
2. Variable Space (Recursion Stack): For each recursive call, the stack must store the return address and local parameters.
3. Depth of Recursion: The function calls itself $n$ times (from $n$ down to $0$).
4. Result: Since the depth of the recursion tree is $n$, and each stack frame takes $O(1)$ space, the total Space Complexity is $O(n)$.

Example 4: Analyze the complexity of the following function (University Question)

void function(int n) {
    int count=0;
    for(int i=n/2; i<=n; i++)
        for(int j=1; j<=n; j=2*j)
            for(int k=1; k<=n; k=k*2)
                count++;
}

1. Outer Loop ($i$): Runs from $n/2$ to $n$.
   • Number of iterations $= n - n/2 + 1 \approx n/2$.
   • Complexity: $O(n)$.
2. Middle Loop ($j$): Starts at 1, doubles each time ($1, 2, 4, 8, \dots, n$).
   • This is a geometric progression. The loop runs $k$ times where $2^k = n \implies k = \log_2 n$.
   • Complexity: $O(\log n)$.
3. Inner Loop ($k$): Same as the middle loop, starts at 1 and doubles until $n$.
   • Complexity: $O(\log n)$.
4. Total Frequency Count:
   • $T(n) = (\text{Outer iterations}) \times (\text{Middle iterations}) \times (\text{Inner iterations})$
   • $T(n) = (n/2) \times (\log n) \times (\log n)$
5. Final Result:
   • $T(n) = O(n \log^2 n)$.