What is the "right" definition of upper and lower bounds?
The right definition of $f(n)=\Omega(n^2)$ is that there exists some $k&gt;0$ such that for infinitely many $n$, $f(n)\geq kn^2$. The infinitely-often definition for lower bounds handles your issues and is how we use it in practice.

I did a post on this back in 2005.

Some textbooks get this definition right, some don't.