Asymptotic Analysis – GATE CSE AlgorithmsPractice Questions & PYQs

(i) TRUE: $n^2 \leq n^3$ for $n \geq 1$. (ii) FALSE: $n^3 / n^2 = n \to \infty$. (iii) TRUE: $2n^2 / n^2 = 2$ (constant). (iv) TRUE: $\lim_{n\to \infty } \frac{n \log n}{n^2} = \lim \frac{\log n}{n} = 0$. So (i), (iii), (iv) are true.

Growth order (slowest to fastest): polynomial $\ll$ exponential $\ll$ factorial $\ll$ $n^n$. Formally: $n^{100} = O(2^n) = O(n!) = O(n^n)$ and $n! = o(n^n)$.

This is the recurrence for Quicksort's average case with a 1/3 - 2/3 split. Using the recursion tree: each level sums to $O(n)$ and the height is $O(\log n)$ (deepest path: $(2/3)^k n = 1 \Rightarrow k = \log_{3/2} n = O(\log n)$). Total: $O(n \log n)$.

2^(√log n) grows slower than other given functions.

O(1) · O(log n) = O(1 · log n) = O(log n). Multiplying complexities follows the product rule.

(i) $O(n^2)$: dominant term is $5n^2$. (ii) $n^2 \log n = \omega(n^2)$: grows faster than $n^2$, so NOT $O(n^2)$. (iii) $n^{1.99} = O(n^2)$. (iv) $100n = O(n^2)$. So (i), (iii), and (iv) are $O(n^2)$.

The maximum element in a sorted array is simply the last element. Accessing the last element takes constant time, hence O(1). Since the array is already sorted, no comparison or traversal is needed.

$a=2, b=2$. $n^{\log_2 2} = n^1 = n$. $f(n) = \Theta(1) = O(n^{1-1}) = O(1)$, so Case 1 applies: $T(n) = \Theta(n^{\log_2 2}) = \Theta(n)$. So $c = 1$.

(i) TRUE: little-omega means strictly faster growth, $\lim f/g = \infty$. (ii) FALSE: little-o means $\lim f/g = 0$ (strictly slower, not faster). (iii) TRUE: $\Theta$ = both $O$ and $\Omega$. (iv) TRUE: transpose symmetry - $f = \Omega(g) \iff g = O(f)$. So (i), (iii), (iv) are correct.

Sum of geometric series: $\sum_{k=0}^{\log n} n^2 (1/2)^k \leq n^2 \sum_{k=0}^{\infty } (1/2)^k = 2n^2 = O(n^2)$. The root dominates (Case 3 of Master Theorem), so $T(n) = \Theta(n^2)$. Hence $x = 2$.

We need $cn \log n - cn + n \leq cn \log n$, i.e., $-cn + n \leq 0$, i.e., $n(1-c) \leq 0$, i.e., $c \geq 1$. So the minimum integer value is $c = 1$.

$T(10) = 1 + 5 \times (10 - 1) = 1 + 45 = 46$. This is a linear (arithmetic) recurrence giving $\Theta(n)$ complexity.

$\log(n^2) = 2 \log n = \Theta(\log n)$. For B: $n^2 \neq \Theta(n^3)$. For C: $2^n / 3^n = (2/3)^n \to 0$ so $2^n \neq \Omega(3^n)$. For D: $n! = o(n^n)$.

B is correct as Theta notation implies both Big-O and Omega. A is incorrect, the relationship is reversed. C is incorrect, the relationship is reversed. D is incorrect, Big-O provides an upper bound.

Big-O notation: $f(n) = O(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq c \cdot g(n)$ for all $n \geq n_0$. It gives an asymptotic upper bound.

$\log_4 64 = \log_4 4^3 = 3$. So $n^{\log_b a} = n^3 = f(n)$. Case 2 of Master Theorem: $T(n) = \Theta(n^3 \log n)$.

Using the aggregate or accounting method: in $n$ operations, at most $O(n)$ total copy work is done during all doublings ($n/2 + n/4 + \cdots \leq n$). Thus amortized cost per operation = $O(n)/n = O(1)$.

Only Case 1 gives $T(n) = \Theta(n^{\log_b a})$. Case 2 gives $\Theta(n^{\log_b a} \log n)$. Case 3 gives $\Theta(f(n))$, not $\Theta(n^{\log_b a})$ unless they're equal. For (iv), $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$. So only (i) gives exactly $\Theta(n^{\log_b a})$.

Correct asymptotic growth order: $\log n \ll \sqrt{n} = n^{0.5} \ll n \ll n \log n \ll n^2 \ll 2^n$. Note: $\sqrt{n}$ grows faster than $\log n$ since $n^{0.5}$ is polynomial and $\log n$ is sub-polynomial.

Let $m = \log n$, so $T(2^m) = T(2^{m/2}) + 1$. Let $S(m) = T(2^m)$: $S(m) = S(m/2) + 1 = O(\log m) = O(\log \log n)$.