Confusion with Big-oh

88 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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