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

closed as off-topic by Jonas Meyer, Claude Leibovici, kjetil b halvorsen, Chappers, user91500 Apr 23 at 9:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jonas Meyer, Claude Leibovici, kjetil b halvorsen, Chappers, user91500
If this question can be reworded to fit the rules in the help center, please edit the 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$. –  Guess who it is. 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. –  Guess who it is. Sep 3 '10 at 2:41

2 Answers 2

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

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

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