0

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

reyna
  • 2,101
Imagin
  • 125

1 Answers1

0

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

marty cohen
  • 107,799