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$$
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$$
$\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$.