# Big O comparison in asymptotic cases

I'm trying to find out if this is a true statement.

Assuming asymptotic cases

$n \sin(n \frac{\pi}{2}) + \log{n} = O(3)$

How would you go about solving a problem like this systematically?

Note: O = "Big O"

Note: lg = log base 2

-
What do you mean by O(3)? It is O(n). –  Jonas Meyer Sep 3 '10 at 2:13
Try expanding the sine as a series, and note that asymptotically $n$ (and higher powers of it) dominates $\log\;n$. –  Ｊ. Ｍ. Sep 3 '10 at 2:16
I don't see how series help. The sine term is bounded. -n < the expression < 2n. –  Jonas Meyer Sep 3 '10 at 2:30
Hmm, you're right Jonas. The factor of $n$ will definitely dominate the sine. –  Ｊ. Ｍ. Sep 3 '10 at 2:41

Note that the notation--the use of $n$ and base-2 logs--indicates this problem comes from computer science, strongly suggesting that $n$ is an integer and we are being asked about the asymptotics as $n$ grows without bound. When $n$ is even, the value is $\log(n)$, but when $n$ is odd, the value is either $n + \log(n)$ or $-n + \log(n)$. Thus the growth equals $\max \left( O(\log(n)), O(-n + \log(n)), O(n + \log(n)) \right) = O(n)$.

It is false that $O(3) \ge O(n)$.

BTW, one wouldn't use an expression like $O(3)$, because the constant is implicit. Conventionally, this is written $O(1)$.

-
Also note the terribly confusing notation used in Computer Science: $O(n) = O(n^2)$, but $O(n^2) \neq O(n)$. What we should be doing is using θ-notation combined with > and < operators, so that we could say $θ(n) < θ(n^2)$ and $θ(n^2) > θ(n)$. Also, we should be writing $n+1\ is\ θ(n)$. Instead, right now we say $n+1 = θ(n)$, which is confusing since the statement $θ(n) = n+1$ really has no meaning. –  BlueRaja - Danny Pflughoeft Sep 3 '10 at 19:33
Thank you whuber and BlueRaja –  Sev Sep 5 '10 at 8:10
@BlueRaja-DannyPflughoeft: I agree that notation is confusing, however, there's hope, as nowadays people are switching to use the more accurate "$\in$" instead of "$=$", i.e., $O(n) \subset O(n^2)$ in many computer science papers. –  Peter Apr 16 '12 at 15:21

If $f(n)=O(g(n))$, with $g(n)>0$ means that there is a a constant $M>0$ that $|f(n)|\leq Mg(n)$ for every $n$, then (if you meant $O(n)$) we must show that there is a constant $M>0$ that $|n\sin{(n\pi/2)}+\log{n}|\leq Mn$ for every $n$. But $|n\sin{(n\pi/2)}+\log{n}|\leq |n\sin{(n\pi/2)}| + \log{n}\leq n +\log{n}\leq 2n$ (for $n> 1$), therefore $M=2$ will do if $n>1$. For the case $n\to 0$, divide the inequality to prove by $n$ and note that $(\log{n})/n\to\infty$ when $n\to 0$, so it can't be true.

-
A little comment, choosing $n = 4k + 1$ we will have $\sin(n\pi/2)=1$, so that the estimate becomes $n\sin(n\pi/2)+\log n = n + \log n\geq n$. Hence $O(n)$ can not be improved. –  AD. Sep 3 '10 at 4:09
Thanks AD and Weltschmerz for the explanations –  Sev Sep 5 '10 at 8:10