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

This recurrence has two recursive calls of unequal sizes, so the standard Master Theorem does not apply directly — use the Akra–Bazzi method.

Write the recurrence in Akra–Bazzi form $T(x) = \sum_i a_i\, T(b_i x) + g(x)$ with

$a_1 = 2,\ b_1 = \tfrac{1}{2}, \qquad a_2 = \tfrac{8}{9},\ b_2 = \tfrac{3}{4}, \qquad g(x) = \Theta\!\left(\frac{x^2}{\log x}\right).$

Step 1 — find $p$ solving $\sum_i a_i b_i^{\,p} = 1$. Try $p = 2$:

$2\left(\tfrac{1}{2}\right)^2 + \tfrac{8}{9}\left(\tfrac{3}{4}\right)^2 = 2\cdot\tfrac{1}{4} + \tfrac{8}{9}\cdot\tfrac{9}{16} = \tfrac{1}{2} + \tfrac{1}{2} = 1.$

So $p = 2$.

Step 2 — evaluate the Akra–Bazzi integral:

$T(x) = \Theta\!\left(x^{p}\left(1 + \int_1^{x} \frac{g(u)}{u^{\,p+1}}\,du\right)\right) = \Theta\!\left(x^{2}\left(1 + \int_1^{x} \frac{u^2/\log u}{u^{3}}\,du\right)\right).$

Simplify the integrand:

$\int_1^{x} \frac{1}{u\,\log u}\,du = \log(\log u)\Big|^{x} = \Theta\big(\log(\log x)\big).$

Step 3 — combine. The $\log(\log x)$ term dominates the constant $1$, so

$T(x) = \Theta\big(x^{2}\,\log(\log x)\big).$

This is option 3.

Exam trick: When you see two divide-and-conquer terms whose split sizes differ ($x/2$ and $3x/4$ here), reach for Akra–Bazzi. After finding $p$, an integral of the form $\int \frac{du}{u\log u} = \log\log u$ is the classic source of a $\log\log$ factor — the same pattern that makes the Master-Theorem watershed case ($g(x)=\Theta(x^p\log^{-1}x)$) produce $\Theta(x^p\log\log x)$.