Asymptotic Analysis – GATE CSE AlgorithmsPractice Questions & PYQs

To compare $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$, we examine the limit of their ratio as $n \to \infty$:
$\lim_{n \to \infty } \frac{g(n)}{f(n)} = \lim_{n \to \infty } \frac{n(\log n)^{10}}{n^2 \log n} = \lim_{n \to \infty } \frac{(\log n)^9}{n}$
Since any power of a logarithm, $(\log n)^k$, grows strictly slower than any linear power of $n$ (i.e., $\lim_{n \to \infty } \frac{(\log n)^k}{n^\epsilon} = 0$ for $\epsilon > 0$), we have:
$\lim_{n \to \infty } \frac{(\log n)^9}{n} = 0 \implies g(n) = o(f(n)) \implies g(n) = O(f(n))$
Conversely, for the reverse ratio:
$\lim_{n \to \infty } \frac{f(n)}{g(n)} = \lim_{n \to \infty } \frac{n}{(\log n)^9} = \infty \implies f(n) \neq O(g(n))$
Thus, $g(n)$ is asymptotically bounded by $f(n)$, but $f(n)$ is not bounded by $g(n)$.

For a sorted array $S$ in ascending order, the two smallest elements are $S[0]$ and $S[1]$. To determine if any two elements sum to less than $1000$, we only need to check if the sum of the two smallest elements satisfies the condition $S[0] + S[1] < 1000$. If this condition holds, such a pair exists; otherwise, since the array is sorted, any other pair $S[i] + S[j]$ (where $i \neq j$) will satisfy $S[i] + S[j] \geq S[0] + S[1] \geq 1000$. Accessing these two elements and performing a single addition takes constant time, thus $T(n) = O(1)$.

Simplify $g(n) = 2^{\sqrt{n} \log_2 n} = (2^{\log_2 n})^{\sqrt{n}} = n^{\sqrt{n}}$.
Given $f(n) = 3n^{\sqrt{n}}$, we observe that $f(n) = 3 \cdot g(n)$.
Because $f(n) \leq 3g(n)$ for all $n$, it follows that $f(n) = O(g(n))$, confirming option D is true.
For $h(n) = n!$, we know $n!$ grows significantly faster than $n^{\sqrt{n}}$ (since $\log(n!) \approx n \log n > \sqrt{n} \log n$), so $h(n)$ is not $O(f(n))$ or $O(g(n))$, making A and B false.
Finally, since $g(n) = \frac{1}{3}f(n)$, $g(n) = O(f(n))$, which makes C false.

(M) $T_n = T_{n-1} + n$ is an arithmetic series summation: $T_n = \sum_{i=1}^n i = \frac{n(n+1)}{2} = O(n^2)$, matching (W).
(N) $T_n = T_{n/2} + n$ follows the Master Theorem with $a=1, b=2, f(n)=n$. Since $f(n) = n^1$ and $n^{\log_2 1} = n^0$, it falls under Case 3, giving $T_n = O(n)$, matching (U).
(O) $T_n = T_{n/2} + n \log n$. Expanding gives $T_n = \sum_{i=0}^{\log_2 n} \frac{n}{2^i} \log(\frac{n}{2^i})$, which converges to $O(n \log n)$, matching (V).
(P) $T_n = T_{n-1} + \log n$ is $T_n = \sum_{i=1}^n \log i = \log(n!) = O(n \log n)$, matching (V).
The correct mapping is M-W, N-U, O-V, P-V.

The recurrence $T(n) = 2T(\lfloor n/2 \rfloor) + \sqrt{n}$ fits the Master Theorem form $T(n) = aT(n/b) + f(n)$ with $a=2$, $b=2$, and $f(n) = \sqrt{n} = n^{0.5}$.
We evaluate the dominant term $n^{\log_b a} = n^{\log_2 2} = n^1 = n$.
Comparing $f(n) = n^{0.5}$ with $n^{\log_b a} = n$, we observe that $f(n) = O(n^{1-0.5})$, which corresponds to Case 1 of the Master Theorem.
This results in $T(n) = \Theta(n^{\log_b a}) = \Theta(n)$.
Since $T(n) = \Theta(n)$, it follows that $T(n) = O(n)$, making option B correct.

A is true because constants do not change the complexity class, so $100n \log n = O(n \log n)$ and $\frac{n \log n}{100} = O(n \log n)$.
C is true because for $y > x$, $n^y$ dominates $n^x$, satisfying the definition of Big-O.
D is true since exponential growth $2^n$ strictly dominates any polynomial growth $n^k$, thus $2^n \neq O(n^k)$.
B is false; let $u = \log n$. As $\sqrt{u}$ grows faster than $\log u$, the limit $\lim_{u \to \infty } \frac{\sqrt{u}}{\log u} = \infty$.
Therefore, $\sqrt{\log n}$ cannot be bounded by $O(\log \log n)$.

To determine the growth rates, we use the definition that $g(n) = O(f(n))$ if $g(n) \leq c \cdot f(n)$ for some constant $c$ and all $n \geq n_0$.

1. For Option A: For $n > 10,000$, $g_1(n) = n^2$ and $g_2(n) = n^3$. Since $n^2 \leq n^3$ for all $n \geq 1$, we have $g_1(n) \leq 1 \cdot g_2(n)$, thus $g_1(n) = O(g_2(n))$.
2. For Option B: $g_1(n)$ is either $n^3$ (for $n \leq 10,000$) or $n^2$ (for $n > 10,000$). In both cases, $g_1(n) \leq 1 \cdot n^3$ holds for all $n \geq 0$, so $g_1(n) = O(n^3)$.
3. For Option C and D: For $n > 10,000$, $g_2(n) = n^3$. Since $n^3$ grows strictly faster than $n^2$ (from $g_1$) and $n$, no constant $c$ satisfies $n^3 \leq c \cdot n^2$ or $n^3 \leq c \cdot n$ for all sufficiently large $n$.

[CORRECT_OPTION: A, B]

The summation $\sum_{1 \leq k \leq n} O(n)$ represents adding a term of order $n$, $n$ times:
$\sum_{k=1}^{n} O(n) = n \cdot O(n) = O(n^2)$
In Big-O notation, constants do not affect the asymptotic growth rate, so $O(3n^2)$ and $O(1.5n^2)$ are equivalent to $O(n^2)$. Additionally, Big-O notation defines an upper bound; any function that is $O(n^2)$ also satisfies $O(n^3)$ because $n^2$ grows slower than $n^3$. Therefore, options B, C, D, and E are all mathematically valid representations of the upper bound.

[CORRECT_OPTION: B, C, D, E]

n^(log n) grows faster than (log n)^(log n), so g(n) = O(f(n)).

$\log_4 4096 = \log_4 4^6 = 6$. The recursion tree has 6 levels (depths 0 through 5), and $T(n) = \Theta(\log_4 n) = \Theta(\log n)$.

The Master Theorem requires $a \geq 1$. In option C, $a = 0.5 < 1$, which violates the requirement that the number of subproblems is at least 1. Option B has a gap between cases but can be solved with extended Master Theorem.

(i) TRUE: Reflexivity holds. (ii) TRUE: $\Theta$ is symmetric - if $f = \Theta(g)$ then $g = \Theta(f)$. (iii) TRUE: $\Theta$ is transitive. (iv) FALSE: $f = \Theta(g)$ means BOTH $O$ and $\Omega$; it does not exclude $\Omega$. Properties (i), (ii), (iii) make $\Theta$ an equivalence relation.

Master Theorem: $a=7, b=2, f(n)=n^2$. $n^{\log_2 7} \approx n^{2.807}$. Since $f(n)=n^2 = O(n^{\log_2 7 - \epsilon})$ for $\epsilon \approx 0.807$ (Case 1), $T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$.

Expanding: $T(n) = \log n + \log(n-1) + \cdots + \log 1 = \log(n!)$. By Stirling's approximation: $\log(n!) = \Theta(n \log n)$. So $O(\log n!) = O(n \log n)$; both A and B are equivalent.

(i) $\Theta(n \log n)$ - Case 2 of Master Theorem. (ii) $\Theta(n^2 \log n)$ - not $n \log n$. (iii) $T(n) = 2T(n/2) + n \log n$: extended Case 2 gives $\Theta(n \log^2 n)$ - not $n \log n$. (iv) $\Theta(n \log n)$ by recursion tree. So (i) and (iv). Correction: (iii) gives $\Theta(n \log^2 n)$. Answer: (i) and (iv) = option B.

$n^2 \sin^2(n)$ oscillates between 0 and $n^2$, so $f(n)$ is not always $\geq c n^2$ (when $\sin(n) \approx 0$, $f(n) \approx n$). Thus $f(n) = O(n^2)$ but $f(n) \neq \Omega(n^2)$, so $\Theta(n^2)$ does not hold.

In Case 3 of the Master Theorem, $f(n)$ dominates the recursion tree cost, so $T(n) = \Theta(f(n))$. Case 1: root is dominated → $\Theta(n^{\log_b a})$. Case 2: balanced → $\Theta(n^{\log_b a} \log n)$.

Polynomial always dominates polylogarithmic. n^1.5 grows faster than n·(log n)^10, so g(n)=O(f(n)).

$g(n) > f(n) = 2^{30}$ when $n^2 > 2^{30}$, i.e., $n > 2^{15} = 32768$. So for $n \geq 32769$, $n^2 > 2^{30}$. This shows constants matter for small $n$ even though $n^2 = O(1)$ is false - $n^2 = \omega(2^{30})$.

If $f(n) \leq c \cdot g(n)$ (i.e., $f = O(g)$), then $g(n) \geq (1/c) f(n)$ (i.e., $g = \Omega(f)$). So $f = O(g) \iff g = \Omega(f)$. This is the transpose symmetry property.