1
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ Just go ahead. By the way, $log(n^2)$ is also $O(log n)$. $\endgroup$
    – Mihai
    Mar 8 '16 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$
    – Raphael
    Mar 8 '16 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$ Mar 8 '16 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$ Mar 9 '16 at 1:00
5
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ That formula does not make any sense; you can not divide infinity by infinity. I guess you want to propose what's explained here? $\endgroup$
    – Raphael
    Mar 8 '16 at 19:57
  • 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$ Mar 8 '16 at 20:27
  • $\begingroup$ @Raphael Yes, I'm sorry I meant $\log$ of course! $\endgroup$ Mar 8 '16 at 23:29
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ and $\log(1 + 1/n) < 2 < \log n$ if $n$ is large enough, done. $\endgroup$
    – vonbrand
    Mar 9 '16 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$
    – wythagoras
    Mar 9 '16 at 17:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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