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

Step 1 — Cost of f1(n)

The loop for(x=0, i=0; i<n; i++) x++ executes the body exactly $n$ times, so

$f1(n) = \Theta(n).$

Step 2 — Set up the recurrence for f2(n)

For $n>0$, f2 makes two recursive calls on inputs of size $n/2$, plus one call to f1(n) (which costs $\Theta(n)$) and $\Theta(1)$ for the additions:

$T(n) = 2\,T\!\left(\tfrac{n}{2}\right) + \Theta(n), \qquad T(0) = \Theta(1).$

Step 3 — Apply the Master Theorem

Here $a = 2$, $b = 2$, and $f(n) = \Theta(n)$. The watershed function is

$n^{\log_b a} = n^{\log_2 2} = n^{1} = n.$

Since $f(n) = \Theta(n) = \Theta\!\left(n^{\log_b a}\right)$, we are in Case 2 of the Master Theorem, which adds a logarithmic factor:

$T(n) = \Theta\!\left(n^{\log_b a}\log n\right) = \Theta(n\log n).$

This is exactly the merge-sort style recurrence: $\log n$ levels of recursion, each doing $\Theta(n)$ total work.

Hence the time complexity of f2 is $O(n\log n)$ — option 3.

Exam trick: The recurrence $T(n)=2T(n/2)+\Theta(n)$ is the canonical merge-sort recurrence; recognize it on sight as $\Theta(n\log n)$ without re-deriving the Master Theorem.