Big O proof for logarithmic function

Question

Taking a class in discrete math and going through one of the textbook examples, I am asked to prove that

$T(n)$ is $O(\log{}n)$

Where $T(n)= 5\log_{2} (2n) +7$. I understand that this means that I must prove that $5\log_{2} 2n +7 \leq\lambda \log(n)$ for some $\lambda$, for $n$ in a neighborhood of infinity. How exactly would I proceed with this?

Answer 1

You can use some simple rules to work with O.

First rewrite $T(n)$ as $5(1+\log n)+7=5\log n+12$. Then combine these rules:

• $12=O(1)$, and $f=O(1)\implies f=O(\log n)$
• $5\log n=O(\log n)$ by definition
• $O(\log n)+O(\log n)=O(\log n)$

Detailed computations:

$12<\log n$ for $n>2^{12}=4096$, hence $T(n)<6\log n$ for $n>4096$.

Answer 2

You can write inequality as $\lambda \geq 5+\frac{12}{\log_2 n}$ which is satisfied by all $\lambda \geq 17$ and constant $n_0=2$. This gives a tight upper bound and also proves that $T(n)=O(\log_2 n)$.

Answer 3

Solve

$$\lambda\ln n\ge5\frac{\ln n+\ln2}{\ln 2}+7$$ or

$$\lambda\ge\frac5{\ln 2}+\frac{12}{\ln n}.$$

As of $n=2$, $\lambda=25>\dfrac{17}{\ln 2}$ is good enough.