سوال ۵۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۲

The inner loop body runs once for each $j$ from $1$ to $\left\lfloor n/i \right\rfloor$, so for a fixed outer index $i$ it executes $\left\lfloor n/i \right\rfloor$ times. The total number of basic operations is therefore

$T(n)=\sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor .$

Drop the floor (it changes each term by at most $1$, contributing only $O(n)$ overall):

$\sum_{i=1}^{n}\frac{n}{i}=n\sum_{i=1}^{n}\frac{1}{i}=n\,H_{n},$

where $H_{n}=\sum_{i=1}^{n}\tfrac{1}{i}$ is the $n$-th harmonic number. The harmonic number satisfies

$H_{n}=\ln n+\gamma+O\!\left(\tfrac{1}{n}\right)=\Theta(\log n).$

Hence

$T(n)=n\,H_{n}+O(n)=\Theta(n\log n).$

The matching answer is option 3, $\Theta(n\log n)$.

Pitfall: A bound of $\left\lfloor n/i \right\rfloor$ on the inner loop is the textbook signature of the harmonic sum, giving $\Theta(n\log n)$ — NOT $\Theta(n^{2})$. The naive guess $n\cdot n=n^{2}$ wrongly assumes the inner loop runs $\Theta(n)$ times for every $i$, but it shrinks as $i$ grows.

Note on the answer key: the preliminary key marks option 2 ($\Theta(n^3)$), but the double loop runs $\sum_{i=1}^{n}\lfloor n/i\rfloor = n H_n = \Theta(n\log n)$ — option 3.