0

I want to estimate big-O notation for $\frac{\log(8n^2)}{\log(n)}$.

I think the big-O notation is constant. am I right?

in case of $\frac{\log(N+1)}{\log(N)}$, is it the same and O(1)?

and what about $\frac{\log(N^3+7n+1)}{\log(N^4+N^2)}$, is it O($\log$ $n$)?

It would be appreciated if somebody could generalize the method of estimating big-O notation of fractions.

Bernard
  • 175,478
David
  • 153

2 Answers2

1

Yes, you're right. The simplest way to see all this is to use equivalents:

  • $\log(8n^3)=\log 8+3\log n\sim_\infty 3\log n$, so $$\frac{\log(8n^3)}{\log n}\sim_\infty\frac{3\log n}{\log n}=3,$$ hence it is $O(1)$.
  • $n^3+7n+1\sim_\infty n^3 $, hence $\log(n^3+7n+1)\sim_\infty \log(n^3)=3\log n $,
  • similarly $\log(n^4+n^2)\sim_\infty 4\log n$,

so $\;\dfrac{\log(n^3+7n+1)}{\log(n^4+n^2)}\sim_\infty \dfrac{3}{4}=O(1)$.

Bernard
  • 175,478
1

In general, for any two polynomials with complex coefficients, $\dfrac{\log|P(n)|}{\log|Q(n)|} =O(1) $ as $n \to \infty$.

You can go further and show that $\dfrac{\log|P(n)|}{\log|Q(n)|} =\dfrac{u}{v}+o(1) $ where $u$ and $v$ are, respectively, the degrees of $P$ and $Q$.

marty cohen
  • 107,799