Asymptotic notation (big Theta)

Question

I'm currently in the process of analyzing runtimes for some given code (Karatsuba-ofman algorithm).

I'm wondering if I'm correct in saying that $\Theta(\left\lceil n/2\right\rceil) + \Theta(n)$ is equal to $\Theta(n)$? (Taking the maximum of both costs)

I know that $\Theta(n/2) +\Theta(n)$ is equal to $\Theta(n)$. But my concern with the first asymptotic runtime is that given $n = 0.6, \left\lceil n/2\right\rceil$ would be equal to $1$, which is greater than $0.6$.

If $\Theta(\left\lceil n/2\right\rceil) + \Theta(n) \stackrel{?}{=} \Theta(n)$ could anybody please give some insight on why this is true?

Answer 1

Yes you are right.. intuitively it's clear that it does not change a thing, since when $n \to \infty$ effects like this are definitely too small to notice.

The whole concept behind asymptotics is that we ignore small terms.. sometimes we can even ignore something "huge" like $2^n$, for example $\Theta(2^n + 3^n) = \Theta(3^n)$

So we don't really care about effect like this; yes if $n=0.6$ you would get $1$, but the error is at most $1/2$ which is not relevant. if you had $n = 10^9 + 0.6$, would you be worried about wether the result is rounded up or down?

---

If you want to be a little bit more formal you can start noting that $\lfloor \frac n2 \rfloor \le n$, and $\Theta(n) + \Theta(n) = \Theta(n)$

Or you can also notice that the error from rounding is at most $1/2$ or $1$, depends on the rounding that one uses and find some bonds from there.

Answer 2

Remember that $f(n) =\Theta (g(n)) $ means that there are positive constants $a$ and $b$ such that $a g(n) < f(n) < b g(n) $ for all large enough $n$.

Therefore, if $f(n) =\Theta (h(n)) $ and $g(n) =\Theta (h(n)) $ then $f(n)+g(n) =\Theta(h(n)) $.

Answer 3

If you consider the problem for the natural numbers it is true that $\Theta(\lceil n/2 \rceil) = \Theta (n)$. As $ \lceil n/2 \rceil \le n \le 2 \lceil n/2 \rceil$. And as a consequence also $\Theta(\lceil n/2 \rceil) + \Theta (n)= \Theta (n)$.

However, if you consider it for the positive real numbers (as $n \to 0$) as your example $0.6$ might suggest then it is not true that $\Theta(\lceil n/2 \rceil) = \Theta (n)$ and neither is $\Theta(\lceil n/2 \rceil) + \Theta (n)= \Theta (n)$. In this case $n = O (\lceil n/2 \rceil)$ as $n \le 2 \lceil n/2 \rceil$ still holds. Yet as $\lceil n/2 \rceil = 1$ for all $0< n \le 2$ we get that $\lceil n/2 \rceil$ is not $O(n)$ as $n \to 0$.