What is the "right" definition of upper and lower bounds? Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.


So, what is the lower bound of the problem? The way I understood it is just the lower bound of $f(n)$. But we know that $f(n) = \Omega(n^2)$ implies that there exists constant $k$, $n_0$ such that for all $n &gt; n_0$, $f(n) &gt; kn^2$, which is not true. Thus it seems that we can only say $f(n) = \Omega(n)$. 
But usually, we will call the problem has a lower bound of $\Omega(n^2)$, right?
Assuming that $g(n) = \Omega(n^2)$, which means that there exists constant $k$, $n_0$ such that for all $n &gt; n_0$, $g(n) &gt; kn^2$. Let's also assume a problem has running time $g(n)$. If we can reduce this problem for all the primes $n$ to another problem (with same input size), can we say the running time of the other problem has a lower bound of $\Omega(n^2)$?
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.