Proving $\log(n+k)$ is $O(log(n))$ for an arbitrary constant $k$?

Question

I must only use the definition of Big O:

$f(n)$ is $O(g(n))$ iff there are constants $C > 0$ and $N > 0$ such that for all $n > N$, $f(n) \leq Cg(n)$.

I know how to do this using limits, but that is not allowed for this problem--we must come up with a constant of sorts. I've tried making $C=log(b)$, but that really doesn't get me anywhere.

Answer 1

Since $$n+k\leq n+n=2n\leq n\cdot n= n^2$$ for all integers $n\geq \max\{k,2\}$, it follows that $$ \log(n+k)\leq \log(n^2)=2\log n$$ for all $n\geq \max\{k,2\}$.

Answer 2

The log function is monotonic increasing because $\log x=\int_1^x\frac {1}{y}\;dy$.

For $x\geq 0$ we have $\log (1+x)=\int_1^{1+x}\frac {1}{y}\;dy \leq \int_1^{1+x}1\;dy=x.$

So for $n>2|k|$ we have $$(\log n)-\frac {|k|}{n-|k|}\leq$$ $$\leq\log n-\log \left(1+\frac {|k|}{n-|k|}\right)=$$ $$=\log (n-|k|)\leq \log (n+k)\leq \log (n+|k|)=$$ $$=\log n+\log \left(1+\frac {|k|}{n}\right)\leq$$ $$\leq (\log n)+\frac {|k|}{n}.$$ Dividing by $\log n$ when $n\geq\max (e^2,2|k|)$ we have $$\frac {1}{2}\leq 1-\frac {1}{\log n}\leq 1-\frac {|k|}{n-|k|}\cdot \frac {1}{\log n}\leq $$ $$\leq \frac {\log (n+k)}{\log n}\leq 1+\frac {|k|}{n\log n}\leq 1+\frac {|k|}{e^2\log n}\leq 1+\frac {|k|}{2e^2}.$$