# Asymptotic notation (big Theta)

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?

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.

• Thanks alot for this explanation. Just as I thought. That's really cleared some things up. – user220506 Mar 2 '15 at 22:12
• @Tazman You're welcome! :) – Ant Mar 2 '15 at 22:13
• Although you stated floor(n/2) <= n, this wouldn't be the case for ceiling(n/2) <= n unless we state for all n >= 1 right? – user220506 Mar 2 '15 at 22:14
• @Tazman yes of course. But then again we only look about what happens in the long run, so to speak, so most of the time I don't even notice I take this assumption and most of what I write is valid for $n$ large enough ;-) – Ant Mar 2 '15 at 22:16
• Okay, that makes sense. Just like if it were a big-O or big-Omega question, we would state some given bound where we see the said behaviour. Thanks for the clarification :) – user220506 Mar 2 '15 at 22:17

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

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

• So Tazman should say $n \to \infty$ if he means that. (Presumably he does, for analyzing "runtimes".) – GEdgar Mar 2 '15 at 22:08
• @GEdgar Well, yes and no. Note they mention the case $n=0.6$ explicitly. But I did mention the result for the integers first. It is however not really necessary to say $n \to \infty$ one just has to make the domain precise, if it is the natural numbers it is fine. The $O$ notation as well as $\Theta$ makes sense without making a limit point precise, as opposed to $o$. Finally note it is the second question of this form I answered today, and there is thus additional reason why I insist on discussing the distinction i make. – quid Mar 2 '15 at 22:13
• The n in question refers to a length of a given number, so I think it's safe that in my answer to the question, one can assume that n consists of natural numbers, and thus theta(ceiling(n/2)) = theta(n). – user220506 Mar 2 '15 at 22:16
• @quid, yes, that's true. I should have been more clear and stated that I was giving that generic example to better my understanding of exactly why it is (or not) equal. – user220506 Mar 2 '15 at 22:19
• @Tazman yes, if it is for integers then you can say this (as I said in my answer). And this is a reasonable assumption given your context. I only discussed the other case since you mentioned $n=0.6$ and there is an actual difference in another situation. [This is an expanded version.] – quid Mar 2 '15 at 22:20