0
$\begingroup$

So, big-oh means:

for at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a

So let's evaluate the statement $1 = \mathcal{O}\log(n)$

We want to show that $1 < k \log(n)$. Now, lets say we choose $k$ to be some very large value. Let $k = 1000000$. So we have $1 < 1000000\log(n)$

For some extremely small value of $n$, maybe $n = 10^{-15}$, the inequality doesn't hold. And we could keep looking at smaller and smaller values of $n$ which would make the inequality false no matter how large the constant $k$ is.

But, going by the definition it looks like we don't have to worry about these extremely small values of $n$. The way I understand it, we get to define some constant $a$ such that we need only look at values of $n > a$. In this case we could just say $a = 1000$ and the inequality will hold for all values of $n > a$. Am I understanding this correctly?

$\endgroup$
1
  • 1
    $\begingroup$ It looks as if you understand. Note we can take $k=1$ and $a= 3$. $\endgroup$ Aug 26, 2014 at 18:36

1 Answer 1

1
$\begingroup$

You're correct. To prove that $f(n) = \mathcal{O}(g(n))$, it suffices to find two particular constants $k$ and $a$ that satisfy the desired inequality. We need to be clever in how we choose these two constants. It's possible to make very poor choices for $k$ and $a$, but that doesn't invalidate what we did, since it doesn't have to hold for any $k$ or for any $a$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .