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

The value of $k$ equals the total number of inner-loop iterations summed over all values of $i$.

Counting the inner loop for a fixed $i$

For a fixed outer value $i$, the inner loop starts at $j = 1$ and advances by a step of $i$ each time, running while $j < n$:

$j = 1,\; 1+i,\; 1+2i,\; \dots$

The number of iterations is

$\left\lceil \frac{n-1}{i} \right\rceil = \Theta\!\left(\frac{n}{i}\right).$

Summing over all $i$

Adding the contributions for $i = 1, 2, \dots, n-1$:

$k \;=\; \sum_{i=1}^{n-1} \Theta\!\left(\frac{n}{i}\right) \;=\; \Theta\!\left(n \sum_{i=1}^{n-1} \frac{1}{i}\right) \;=\; \Theta\big(n \cdot H_{n-1}\big).$

The harmonic number satisfies $H_{n-1} = \Theta(\log n)$, so

$k = \Theta(n \log n).$

The harmonic sum is the key: the inner loop does not run $\Theta(n)$ times for every $i$ — it runs only $\Theta(n/i)$ times, and $\sum 1/i$ grows like $\log n$, not like $n$. That is why the total is $n\log n$ and not $n^{2}$.

Numerically, dividing the exact count by $n^{2}$ tends to $0$ as $n$ grows, while dividing by $n\log n$ stabilizes near a constant — confirming $\Theta(n\log n)$.

Pitfall: Two nested loops up to $n$ do not automatically give $\Theta(n^{2})$. Here the inner step size grows with $i$, shrinking the inner count to $\Theta(n/i)$ and collapsing the double sum into a harmonic series $\Theta(n\log n)$. (Strictly, the literal $i=0$ pass keeps $j$ fixed; the intended analysis takes $i \ge 1$, where the step is meaningful.)