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?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ Just go ahead. By the way, $log(n^2)$ is also $O(log n)$. $\endgroup$– MihaiCommented Mar 8, 2016 at 19:37
-
1$\begingroup$ I don't understand the question. What do you mean by "simplify"? When are you ever allowed to change the left side? $\endgroup$– RaphaelCommented Mar 8, 2016 at 19:39
-
$\begingroup$ @Raphael I assume "simplify" in the sense of manipulating the expression $\log(n+1)$ to get something simpler. (E.g., $(x+1)^2-(x-1)^2$ simplifies to $4x$.) $\endgroup$– David RicherbyCommented Mar 8, 2016 at 22:34
-
$\begingroup$ Or it might be a more involved view of "simplification" that applies specifically to considerations of Big-O. For example, you might say that if $g(x)$ is $O(f(x))$, then $f(x) + g(x)$ "simplifies" to $f(x)$ in this context, and so $x^2 + x$ simplifies to $x^2$. Of course you have to be careful to apply correctly the theorems that have given you such "simplification rules". $\endgroup$– Steve JessopCommented Mar 9, 2016 at 1:00
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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$?
answered Mar 8, 2016 at 21:15
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
44k8 gold badges118 silver badges184 bronze badges
$\begingroup$
$\endgroup$
3
Simplify is only necessary if you can show the same with less steps. Here simplifying will not spare you something.
You can either find a $c$ and $n$ or you could use limit value.
$$ v = \lim_{n\to\infty}{\frac{\log(n+1)}{\log(n)}} $$
and if the limits exist ($v < \infty$) then $\log(n+1)\in O(\log(n))$.
-
3
-
1$\begingroup$ Also, what do you mean by "$\lim(n)$"? Do you mean something like $\lim_{n\to\infty}f(n)$, where $f$ is some function such as $\log$? $\endgroup$ Commented Mar 8, 2016 at 20:27
-
$\begingroup$ @Raphael Yes, I'm sorry I meant $\log$ of course! $\endgroup$ Commented Mar 8, 2016 at 23:29
$\begingroup$
$\endgroup$
2
You can simplify the expression as following:
$$\log(n+1)=\log(n)+\log \left(\frac{n+1}{n}\right)$$
It shouldn't be to hard to show that $\log \left(\frac{n+1}{n}\right)<\log(n)$ for $n\geq 2$.
But it doesn't necessarily help to make the process shorter.
However, to solve the problem, you need to rewrite something. This can be done with inequalities or with equalities. In this case, I'd personally prefer to start out with inequalities.
-
$\begingroup$ and $\log(1 + 1/n) < 2 < \log n$ if $n$ is large enough, done. $\endgroup$– vonbrandCommented Mar 9, 2016 at 16:33
-
1$\begingroup$ @vonbrand Exactly, but I usually leave those details out so that the OP can figure them out. Otherwise they won't think about the answer. $\endgroup$ Commented Mar 9, 2016 at 17:08
$\begingroup$
$\endgroup$
$n+1 ≤ n^2$ for $n ≥ 2$, therefore $\log(n+1) ≤ \log (n^2) = 2 \log n$ for $n ≥ 2$, which by definition means $\log(n+1) = O(\log n)$.
“Simplifying” is difficult. Let $f(n) = 2^{2^n}$, then $f(n+1) ≠ O(f(n))$. Same for $f(n) = n!$ Or more difficult to prove when $f(n) = \left|\sin(n)\right|$.
