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$ ?

$\endgroup$

marked as duplicate by Juho, Discrete lizard May 17 at 7:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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 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 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 at 7:19
  • $\begingroup$ @shi95 It's the "limit definition" in the right side of the table on Wikipedia. $\endgroup$ – Juho May 17 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 at 7:35