Question Details

T₁(n) = 4T₁ n2 +n^log₄5. Which is true?

Options

$T_{1} (n) = θ (n^{2})$

$T_{1} (n) = θ (n^{\log ⁴ n})$

$T_{1} (n) = θ (n^{\log 45} \log n)$

$T_{1} (n) = θ (n^{2} \log n)$

Show Answer

Correct Answer :

Option A

$T_{1} (n) = θ (n^{2})$

Solution :

The correct option is:
$T_{1} (n) = θ (n^{2})$

Step-by-Step Explanation:
The given recurrence relation is:
$T_{1} (n) = 4 T_{1} (\frac{n}{2}) + n^{{log}_{4} 5}$

We can analyze this recurrence relation using the Master Theorem, which is applicable to recurrences of the form:
$T (n) = a T (\frac{n}{b}) + f (n)$

By comparing the terms, we identify the parameters:
- Coefficient of the recursive term, a = 4
- Dividing factor of the input size, b = 2
- Non-recursive cost function, f(n) = n^log₄(5)

Next, we compute the critical exponent value:
$n^{{log}_{b} a} = n^{{log}_{2} 4} = n^{2}$

Now we compare f(n) = n^log₄(5) with n^log_b(a) = n².
Since 4 < 5 < 16, we know that:
$1 < {log}_{4} 5 < 2$

The value of log₄(5) is approximately 1.161. Since 1.161 is strictly less than 2, the non-recursive part grows strictly slower than n²:
$f (n) = O (n^{2 - ε})$
for a constant ε = 2 - log₄(5) ≈ 0.839 > 0.

According to Case 1 of the Master Theorem, when the recursive work dominates the non-recursive overhead, the overall time complexity is determined by the recursive work:
$T_{1} (n) = θ (n, {log}_{b} a) = θ (n^{2})$