solving recurrence with $\Theta$: $T(n) = 3T(\frac{n}{2}) + \Theta n$

225 Views Asked by At

Solving Recurrence with $\Theta$

If $f(n)=\Theta n$, what exactly is $f(n)$?
This is what's throwing me off. I'm trying to solve using the master theorem.

$$\mathrm{T}(n) = 3\mathrm{T}(\frac{n}{2}) + \Theta n$$

1

There are 1 best solutions below

0
On

$\Theta(n)$ is a function $f(n)$ for which there are positive constants $a$ and $b$ such that $an < f(n) < bn$ for all large enough $n$.