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

The recurrence relates the value at the cube $n^{3}$ to the value at the previous cube $(n-1)^{3}$. The trick is to unroll over the cube arguments, then change variables back at the end.

Unroll the recurrence. Starting from the argument $n^{3}$ and stepping down through $(n-1)^{3}, (n-2)^{3}, \dots, 1^{3} = 1$:

$T(n^{3}) = T((n-1)^{3}) + \Theta(n) = T((n-2)^{3}) + \Theta(n-1) + \Theta(n) = \cdots$

Each descent peels off one $\Theta(k)$ term, so

$T(n^{3}) = T(1) + \sum_{k=2}^{n} \Theta(k) = 1 + \Theta\!\left(\sum_{k=2}^{n} k\right) = \Theta(n^{2}).$

Change variables. Let $N = n^{3}$, so that $n = N^{1/3}$. Substituting back:

$T(N) = \Theta(n^{2}) = \Theta\!\left((N^{1/3})^{2}\right) = \Theta\!\left(N^{2/3}\right).$

Renaming $N$ to $n$, we get $T(n) = \Theta(n^{2/3})$, which is option 3.

Exam trick: When the recurrence's argument is a function of $n$ (here $n^{3}$, not $n$), sum the costs in the natural variable first ($n^{2}$ here), then translate the answer back into the actual input size via the inverse map ($n \mapsto n^{1/3}$).