1
$\begingroup$

I was wondering about big-theta ($\Theta$) notation.

A) Is $\Theta(n/2) \leq \Theta(n)$ for $n$ being an integer? I know that $n/2 = O(n)$, but does it also mean that $\Theta(n/2) \leq \Theta(n)$?

B) If I add two theta terms, so let's assume, we have: $\Theta(n) + 2*\Theta(n/2) + \Theta(n/3)$. Is that all $\Theta(n)$ or is it $\Theta(n) + \Theta(n/2) + \Theta(n/3)$. Again, for big-oh notation I just take the max when I add them, and I don't know if the same applies to big-theta.

$\endgroup$
0
$\begingroup$

Since $n = O(n/2)$ is also true, as $n \le 2 (n/2)$, you get $\Theta(n)= \Theta(n/2)$.

For B, yes this is all just $\Theta(n)$. Recall the first part and note $\Theta(n)+\Theta(n) = \Theta(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.