0
$\begingroup$

this MIT course gives a formula about Big O

$$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$

going through wiki, i cannot find a similar Big O properties or usages.

how to compute $O(n^{0.000001})$ to get a quantity like $\log n$ ?

Improve this question
$\endgroup$
6
  • $\begingroup$ I suppose what you are referring to is the claim that for any $c > 0$, we have that $\log n = O(n^c)$. You can prove the claim by just applying the the definition of Big Oh. That is, show that $\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} \log n / n^c < \infty$ and you are done. $\endgroup$ – Juho May 17 '19 at 6:58
  • $\begingroup$ This seems to be an exact duplicate of a question you previously asked here. Please do not repost your questions if they are marked as duplicate (or closed for another reason). Instead, edit your question to adress the remarks made and explain why you think the question should be reopened. $\endgroup$ – Discrete lizard♦ May 17 '19 at 7:04
  • $\begingroup$ @Juho i cannot get your point, would plz give more explanation how do you get the right side from left side of $\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} \log n / n^c < \infty$, which part of definition let you do this or unlock my question, so that some one else may give more info easy to understand $\endgroup$ – shi95 May 17 '19 at 7:19
  • $\begingroup$ @shi95 It's the "limit definition" in the right side of the table on Wikipedia. $\endgroup$ – Juho May 17 '19 at 7:21
  • $\begingroup$ @Juho thanks for your reply, do you mean you get this formula from the table on Wikipedia? $$O(n^c) = \lim_{n \to \infty} \frac{\log n }{ n^c} < \infty$$ $\endgroup$ – shi95 May 17 '19 at 7:35