Dark Mode

5,684 views

23 votes

Best answer

Answer: **A**

According to Master theorem,

$T(n) = aT(\frac{n}{b}) + f(n)$ can be expressed as:

$T(n) = [n^{\log_ba}][T(1) + u(n)]$

where $u(n) = \Theta(h(n))$ where $h(n) = \frac{f(n)}{n^{\log_ba}} = \frac{n}{n^{\log_43}} = n^{1-\log_43}$ as $h(n) = n^r$ where $r>0$.

So, $T(n) = [n^{\log_ba}][T(1) + u(n)] = T(n) = [n^{\log_43}][T(1) + \Theta(n^{1-\log_43})] = \Theta(n^{1})$.

17 votes

0