Prove or disprove this Big O and Theta proposition

77 Views Asked by At

It's the problem:

$$\log \left ( \Theta\! \left (\frac{n+1}{n} \right ) \right ) = O( \log n)$$

and I want to show if it's true or not and I know I should use Big O and Theta definition, but I don't know how exactly i can prove or disprove it.

1

There are 1 best solutions below

0
On

HINT: Just use the definition, $$f(n)=\mathcal{O}(g(n))\iff \exists k>0, \exists n_{0}\in \mathbb{N},\forall n<n_{0}: |f(n)|\leqslant k \cdot g(n).$$ and about $\log\left(\Theta\left( \frac{n+1}{n}\right) \right)$ I suppose that you are saying $$\log \left(\Theta\left( \frac{n+1}{n}\right) \right):=f(n)$$ where $f(n)=\log(h(n))$ for some $h(n)\in \Theta\left(\frac{n+1}{n}\right)$ and then use the definition of $\Theta(\cdot)$.