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

The question asks for the order of the final value of $k$, not the running time. We must add up every increment $i+j$ over all executions of the inner loop body.

Setting up the double sum

The outer index $i$ runs from $1$ to $n-1$, and for each $i$ the inner index $j$ runs from $1$ to $i-1$. Each pass adds $i+j$ to $k$:

$k \;=\; \sum_{i=1}^{n-1}\;\sum_{j=1}^{i-1} (i+j).$

Evaluating the inner sum

For a fixed $i$ there are $i-1$ terms:

$\sum_{j=1}^{i-1}(i+j) \;=\; (i-1)\,i \;+\; \sum_{j=1}^{i-1} j \;=\; i(i-1) + \frac{(i-1)i}{2} \;=\; \frac{3\,i(i-1)}{2}.$

Summing over $i$

$k \;=\; \frac{3}{2}\sum_{i=1}^{n-1} i(i-1) \;=\; \frac{3}{2}\sum_{i=1}^{n-1}\big(i^{2}-i\big).$

Using $\sum i^{2} = \Theta(n^{3})$ and $\sum i = \Theta(n^{2})$, the dominant term is cubic:

$k \;=\; \Theta(n^{3}).$

Intuitively, the body runs about $\tfrac{n^{2}}{2}$ times (that is the time complexity, $\Theta(n^{2})$), and each increment $i+j$ is itself $\Theta(n)$, so the accumulated value is $\Theta(n^{2})\cdot\Theta(n)=\Theta(n^{3})$.

Numerically, $k/n^{3}\to\tfrac12$ as $n$ grows (e.g. $0.485$ at $n=100$, $0.4985$ at $n=1000$), while $k/n^{2}\to\infty$ — confirming order $n^{3}$, which is option 3.

Exam trick: Separate time from value. The loops execute $\Theta(n^{2})$ times, but you are asked for the magnitude of $k$. Because each increment $i+j$ grows linearly with $n$, the stored value is one order higher than the iteration count: $\Theta(n^{3})$, not $\Theta(n^{2})$.