Time complexity, proof $\log(n + c) \in O(\log(n))$

Question

I have to prove that for $a \in N, c > 0$ (constants), this statement holds:

$\log_a(n + c) \in O(\log_a(n))$

So if I use the definition, the following should hold:

$\log_a(n + c) \leq d\log_a(n) = \log_a (n^d), \forall n \geq n_0, d > 0$

I have to find $n_0, d$ now

$n + c \leq n^d$

But how can I express $d$ so it depends only on $c$? How to continue from here? Thanks for any help!

Make life simpler. Let $n_0=c$. Then we must have $2c<c^d$. I'm sure you can figure that out ;). For $n>n_0$, you can show that for a given $d$ such that $2c<c^d$ we must have $n+c<n^d$. — ShakesBeer, Sep 07 '14 at 12:41
I wondered that. But we don't care, as $\log(n+c)<\log(n+c+1)$ — ShakesBeer, Sep 07 '14 at 12:53

score 3 · Accepted Answer · answered Sep 07 '14 at 13:14

I'm omitting the $a$ from the notations, as the base of the logarithm doesn't change anything. For fixed $c > 0$, and any $n \geq 1$, $$ \log(n+c) = \log\left(n\left(1+\frac{c}{n}\right)\right) = \log n + \log\left(1+\frac{c}{n}\right)\;. $$ But $\log\left(1+\frac{c}{n}\right) \xrightarrow[n\to\infty]{} 0$, so in particular it is less than $\log n$ (which goes to $\infty$) for $n$ "sufficiently large" (i.e., $\exists n_0, \forall n \geq n_0\; \log\left(1+\frac{c}{n}\right)\leq \log n$). Hence, for $n$ sufficiently large $$ \log(n+c) \leq 2\log n $$ proving the result.

score 3 · Answer 2 · answered Sep 07 '14 at 13:16

3

Perhaps first prove $$ \lim_{n\to\infty} \frac{\log(n+c)}{\log n} = 1 $$

answered Sep 07 '14 at 13:16

GEdgar

111,679

Time complexity, proof $\log(n + c) \in O(\log(n))$

2 Answers2