Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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$. –  J. M. 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. –  J. M. Sep 3 '10 at 2:41
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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