Asymptotic Analysis – GATE CSE AlgorithmsPractice Questions & PYQs

Master Theorem: $a=4, b=2, f(n)=n^2$. $n^{\log_b a} = n^{\log_2 4} = n^2$. Since $f(n) = \Theta(n^{\log_b a})$ (Case 2), $T(n) = \Theta(n^2 \log n)$.

Big-O is transitive. If $f(n) \leq c_1 g(n)$ and $g(n) \leq c_2 h(n)$ for large enough $n$, then $f(n) \leq c_1 c_2 h(n)$, so $f(n) = O(h(n))$.

Exponential functions grow faster than polynomial and logarithmic functions. Hence 2^n grows the fastest.

3n√n = 3n^1.5 is the dominant term. So f(n) = O(n^1.5) is the tightest upper bound.

n² grows slower than n³ ✓. n³ grows faster than n² ✗. 2^(n+1)=2·2^n ∈ O(2^n) ✓ since constant factor is absorbed.

(i) TRUE: $n/n^2 = 1/n \to 0$. (ii) FALSE: $n^2/n^2 = 1 \neq 0$; $f = o(g)$ requires strict inequality. (iii) TRUE: any polylogarithm is $o(n^\epsilon)$ for any $\epsilon > 0$. (iv) FALSE: $2n/3n = 2/3 \neq 0$. So only (i) and (iii).

$T(n) = T(n-2) + 2$. For odd $n$: $T(n) = T(1) + 2 \times \frac{n-1}{2} = 1 + (n-1) = n$. So $T(101) = 101$.

(i) TRUE: $\log^2 n = o(n^{1/2})$. (ii) FALSE: $n^3 / (n^2 \log n) = n / \log n \to \infty$, so $n^3 \neq O(n^2 \log n)$. (iii) TRUE: $2^{3n} = 8^n$; $3^n / 8^n = (3/8)^n \to 0$. (iv) TRUE: $n! \leq n^n$ always. So (i), (iii), (iv).

$\log_9 3 = \log_9 9^{0.5} = 0.5$. So $n^{\log_b a} = n^{0.5} = \sqrt{n} = f(n)$. This is Master Theorem Case 2: $T(n) = \Theta(\sqrt{n} \log n)$.

In asymptotic analysis, lower-order terms and constant coefficients are dropped. The dominant term is $5n^3$. Tightest Big-O = $O(n^3)$. Note: $O(5n^3) = O(n^3)$ since constants are ignored.

Big-O notation describes the upper bound of a function's growth, focuses on the dominant term, and is used for comparing algorithm efficiency. It does not consider best-case scenarios; Big-Omega notation is used for that.

$n^3 = O(n^2)$ is FALSE because $n^3 / n^2 = n \to \infty$, so there is no constant $c$ such that $n^3 \leq c n^2$ for all large $n$. All other statements are true since higher-degree polynomials and exponentials dominate.

By the Master Theorem: $a=2, b=2, f(n)=n$. $n^{\log_b a} = n^{\log_2 2} = n^1 = n$. Since $f(n) = \Theta(n^{\log_b a})$ (Case 2), $T(n) = \Theta(n \log n)$. This is the recurrence for Merge Sort.

(i) Merge Sort: always $\Theta(n \log n)$. (ii) Heap Sort: always $\Theta(n \log n)$. (iii) Bubble Sort: $\Theta(n^2)$ worst/average case. (iv) Quick Sort average: $\Theta(n \log n)$. So (i), (ii), and (iv).

Expanding: $T(n) = n + (n-1) + (n-2) + \cdots + 1 = \frac{n(n+1)}{2} = \Theta(n^2)$. This is $O(n^2)$ which matches the recurrence for selection/insertion sort.

Master Theorem: $a=8, b=2, f(n)=n^2$. $n^{\log_2 8} = n^3$. Since $f(n) = n^2 = O(n^{3-\epsilon})$ for $\epsilon=1$ (Case 1), $T(n) = \Theta(n^3)$. This is the recurrence for naive matrix multiplication.

Growth order: logarithmic < root < n/log n < linear.

The outer loop runs 'n' times. For every iteration of the outer loop, the inner loop runs (n-i) times. In the worst case, this results in approximately n + (n-1) + (n-2) + ... + 1 iterations, which is proportional to n^2.

$\Theta$ (tight bound) means both upper and lower bound: $f(n) = \Theta(g(n))$ iff $f(n) = O(g(n))$ (upper bound) AND $f(n) = \Omega(g(n))$ (lower bound), meaning $g(n)$ is a tight asymptotic bound for $f(n)$.

Little-o notation $f(n) = o(g(n))$ means $\lim_{n \to \infty } \frac{f(n)}{g(n)} = 0$, i.e., $f$ grows strictly slower than $g$. Big-O allows equality ($f$ could equal $g$ up to a constant), but little-o is strictly smaller.