0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks alot for this explanation. Just as I thought. That's really cleared some things up. $\endgroup$ – user220506 Mar 2 '15 at 22:12
  • $\begingroup$ @Tazman You're welcome! :) $\endgroup$ – Ant Mar 2 '15 at 22:13
  • $\begingroup$ 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? $\endgroup$ – user220506 Mar 2 '15 at 22:14
  • $\begingroup$ @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 ;-) $\endgroup$ – Ant Mar 2 '15 at 22:16
  • $\begingroup$ 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 :) $\endgroup$ – user220506 Mar 2 '15 at 22:17
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So Tazman should say $n \to \infty$ if he means that. (Presumably he does, for analyzing "runtimes".) $\endgroup$ – GEdgar Mar 2 '15 at 22:08
  • $\begingroup$ @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. $\endgroup$ – quid Mar 2 '15 at 22:13
  • $\begingroup$ 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). $\endgroup$ – user220506 Mar 2 '15 at 22:16
  • $\begingroup$ @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. $\endgroup$ – user220506 Mar 2 '15 at 22:19
  • $\begingroup$ @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.] $\endgroup$ – quid Mar 2 '15 at 22:20

Your Answer

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