Had a question about the following:
$$\log (n+1) \in O(\log n)$$
Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?
Asked By : TacoB0t
Answered By : Gilles
Simplifying the left-hand side is a good strategy. You aren't going to find a simpler expression that's equal to $\log(n+1)$, though. However, since you're only interested in proving that $\log(n+1)$ is "not too large", it can be a good strategy to find an intermediate step that's larger than $\log(n+1)$ but still not too large. That is, try to find a function $f$ such that $\log(n+1) \le f(n)$ (for sufficiently large $n$), and $f(n) \in O(\log n)$.
(Easy exercise: prove that this is true — if you've found a such a function $f$ then $\log(n+1) \in O(\log n)$.)
So you can try to fill in the statement $\log(n+1) \le \ldots$ with something simpler on the right-hand side. "Simpler" meaning that in the end it'll be simpler to prove that this is in $O(\log n)$. So keep the definition of $O$ in mind: you'll need to prove that $f(n) \le C \log n$ for some $C \gt 0$.
This suggests trying to find $f$ of the form $C \log(n)$.
Hint:
$x + 1 \le x + x$
Hint #2:
You can say that again.
Of course this approach works for other functions and other bounds.
Exercise (open-ended): can you generalize this to $\Omega$? To $\Theta$? To $o$?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/54157
0 comments:
Post a Comment
Let us know your responses and feedback