سوال ۶۷ کنکور ارشد علوم کامپیوتر ۱۴۰۱

We are given $T(2^{n}) = T(2^{n-1}) + \Theta(n^{2}), \qquad T(1) = \Theta(1).$

Step 1 — Define a helper sequence over the exponent. Let $S(n) = T(2^{n})$. Substituting into the recurrence: $S(n) = S(n-1) + \Theta(n^{2}), \qquad S(0) = T(2^{0}) = T(1) = \Theta(1).$ This is a simple subtract-and-conquer recurrence in $n$: each step removes one level and adds a $\Theta(n^{2})$ cost.

Step 2 — Unroll the sum. $S(n) = \Theta(1) + \sum_{k=1}^{n} \Theta(k^{2}) = \Theta\!\left(\sum_{k=1}^{n} k^{2}\right) = \Theta\!\left(\frac{n(n+1)(2n+1)}{6}\right) = \Theta(n^{3}).$ So $S(n) = T(2^{n}) = \Theta(n^{3})$.

Step 3 — Translate back to the original variable. Write $m = 2^{n}$, so $n = \lg m$ (base-2 log). Then $T(m) = S(\lg m) = \Theta\!\left((\lg m)^{3}\right).$ Renaming $m$ back to $n$, the order is $T(n) = \Theta\!\left((\lg n)^{3}\right).$

This matches option 4.

Pitfall: The recurrence is written in terms of the exponent $n$, not the argument size. Plugging $\Theta(n^{2})$ directly into a Master-Theorem template gives $n^{3}$ (option 2), which is the value of $S(n)$ — the answer before substituting $n = \lg m$ back. You must change variables so the order is expressed in the actual input $n$, yielding $(\lg n)^{3}$.