Help solve Recurrence Relation $T(n)=3\cdot T\left(n/2\right)+\Theta(n)$

55 Views Asked by At

Experts, I tried solving this question on my own but not sure about the answer. So, pls check my solution.

The general equation that I've found in terms of $k$ is

$$T(n)=3^k\cdot T\left(\dfrac n{2^k}\right)+c\cdot n\cdot\left(1+3+3^2+3^3+\cdots+3^{k-1}\right)$$

As, $\Theta(n)=c\cdot n$ where $c>0$.

Solving it further,

$$T(n)=3^k\cdot T\left(\dfrac n{2^k}\right)+c\cdot n\cdot\dfrac{3^k-1}2$$ Substituting $k=\log_2n$, $$T(n)=3^{\log_2n}\cdot m+ c\cdot n\cdot\dfrac{3^{\log_2n}-1}2$$ Where, $T(1)=m, m>0$. So, $$T(n)\in\mathcal O\left(n\cdot3^{\log_2n}\right)\quad\text{[Answer]}$$

If you find any mistake, pls point it out. Thanks in advance.

1

There are 1 best solutions below

0
On

Let's try the master method to verify your answer.

Suppose $$T(n) = a\cdot T\left(\dfrac nb\right) + f(n)\tag{1}$$ Then, comparing $(1)$ with your equation, we get that $a = 3, b = 2, f(n) = n$. We need to compare $f(n)$ with $n^{\log_ba}$. $$f(n) = n; \quad n^{\log_ba} = n^{\log_23}\approx n^{1.59}$$ We see that $f(n)=\mathcal O\left(n^{\log_ba}\right)$. We can apply the first case of the master method. Therefore, $$T(n) = \Theta(n^{\log_ba}) = \Theta(n^{\log_23})$$