I'm working on the following asymptotic algorithm bounds problem
- Find a $\Theta$ bound for $f(n) = \frac{n^2}{2} – \frac{n}{2}$
So I could find the big-$O$ bound fairly easily
$$ 0 \leq \frac{n^2}{2} – \frac{n}{2} \leq 1 \cdot n^2 \space\space\space\space \forall \space n >1$$
$$\therefore f(n) = O(n^2)$$
Now I'm having trouble finding the $\Omega$ bound. The solution from my book is listed below
$$ 0 \leq \frac{1}{5} \cdot n^2 \leq \frac{n^2}{2} – \frac{n}{2} \space\space\space\space \forall \space n >1$$
$$\therefore f(n) = \Omega(n^2)$$
I've inputted some values and $\frac{1}{5} \cdot n^2$ makes sense as a lower bound but I don't know how they got the $\frac{1}{5}$
Question: Is there a general strategy for finding bounds aside from just guessing? And, is there an algebraic way to show that there solution is correct?
Thanks for any help
Best Answer
Trust me, you're better off with considering it to be trial-and-error, to the extent you don't have enough experience to consider it "just a bit of boring algebra". Certainly it will be a waste of time to spend any effort formulating and learning a general strategy for finding constants for big-O proofs.
Why? Because after solving a few weeks worth of homework of this kind, you will never have to do it again. It is not a skill that has the slightest practical use for analyzing algorithms -- in fact the very reason to use big-O notation to speak about asymptotic growth is such that one won't have to worry about what these constants are.
The point of setting homework exercises that apply the definitions is simply to make sure you convince yourself in a few easy cases that the definitions make sense and that you can safely stop caring about exactly what the constants are in each particular situation.
Once you've done this, everything else you do with asymptotic analysis will be done by learning a few rules of thumb: The term with the highest exponent always wins. If there are logarithmic factors multiplied onto the powers of the variable, the highest power of the logarithm wins -- but only if the exponent on the variable are equal; even a small fractional difference in the exponent trumps all logarithmic factors. And so on.
Once you've got those rules internalized, you won't have any reason to worry about particular $c$s and $N$s.
In the unlikely case that you end up with a final exam that asks you to find particular $c$s and $N$s, a general approach would be
Pick a $c$ out of thin air such that it looks clearly larger than it needs to be. (For big-$\Omega$ instead of big-O, make it clearly smaller than it needs to be -- this looks like how they got $\frac15$ in your concrete case: it's something picked out of thin air that doesn't look like it will be too large to work).
Using plain old high school algebra, find out how large $N$ has to be to work with the $c$ you have chosen. Don't worry about getting a precise bound; it's allowed to quite an $N$ that is larger than strictly necessary.