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

The question asks for the order of the printed value k, not the running time. Accumulate the contributions:

$k = \sum_{i=1}^{n}\sum_{j=1}^{i} i\cdot j = \sum_{i=1}^{n} i\left(\sum_{j=1}^{i} j\right).$

The inner sum is the triangular number:

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

Substitute back:

$k = \sum_{i=1}^{n} i\cdot\frac{i(i+1)}{2} = \frac{1}{2}\sum_{i=1}^{n}\left(i^{3}+i^{2}\right).$

The dominant piece is $\sum_{i=1}^{n} i^{3} = \left(\frac{n(n+1)}{2}\right)^{2} = \Theta(n^{4})$, while $\sum i^{2} = \Theta(n^{3})$ is lower order. Hence

$k = \frac{1}{2}\left(\Theta(n^{4}) + \Theta(n^{3})\right) = \Theta(n^{4}).$

So the magnitude of the output is of order $n^{4}$, which is option 4.

Pitfall: The running time of this code is only $\Theta(n^{2})$ (the body runs $\sum_{i=1}^{n} i = \Theta(n^{2})$ times). The question instead asks about the size of the value k that is printed — each addition contributes $i\cdot j$, pushing the accumulated value to $\Theta(n^{4})$. Read carefully whether a complexity question is about time or about the computed result.