1
$\begingroup$

I've been working on an asymptotic proof and I want to start with saying that since $\log z=O(z)$ then $\log z\le\frac1 9z$ for $z\ge z_0$. In this example I'm picking $c=\frac1 9$ and hoping $z_0$ exists, but is $z_0$ guaranteed to exist if I pick $c$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let's take as an example $f(n) = g(n) = n$ and $c = 1/2$. Does there exist an $n_0$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$?

In your case, you know more: $\log n = o(n)$. This means that $$ \lim_{n\to\infty} \frac{\log n}{n} = 0, $$ which implies that for every $c$ there exists $n_0$ such that $\frac{\log n}{n} \leq c$ for all $n \geq n_0$.

$\endgroup$
2
  • $\begingroup$ I think this makes sense. Since the limit is approaching zero, for any given $c$ the $n_0$ will be the $n$ where $\frac{\log(n)}{n} = c$? $\endgroup$
    – Brady Dean
    Apr 27, 2021 at 21:22
  • $\begingroup$ You can take this $n_0$ since $\frac{\log n}{n}$ is monotone, but in general you are not guaranteed anything like that. $\endgroup$ Apr 27, 2021 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.