# Big theta notation

I'm trying to figure out the following problem:

If algorithm $$A$$ has a big theta notation of $$n^3$$ and algorithm $$B$$ has a big theta notation of $$n^2$$, there might be an infinite number of inputs for which $$A$$ has a lower running time than $$B$$. Is the statement correct?

My guess is that it's not correct, because big theta notation is bounded from both sides, therefore $$n^3$$ can't be faster than $$n^2$$ for any input.

Is my theory correct?

Thanks

• The title of your question is quite general. Perhaps you could focus it? May 13, 2020 at 15:57
• I do not read infinite number of problem sizes. May 13, 2020 at 22:27

If given an algorithm $$Alg$$, you denote by $$f_{Alg}(n)$$ the maximum running time of $$Alg$$ among all inputs of size $$n$$, your statement is false. Let $$B$$ be an algorithm that just executes an empty loop for $$n^3$$ iterations. Let $$A$$ be an algorithm that checks whether the first bit of the input is even or odd. If it is even, it executes an empty loop for $$n^2$$ iterations. If it is odd, it terminates immediately. According to the above choices, $$f_A(n) = \Theta(n^3)$$, and $$f_B(n) = \Theta(n^2)$$, yet there are infinite inputs for which $$A$$ runs faster than $$B$$ (i.e., essentially all input strings with an odd bit).
In this sense saying that $$f_{Alg}(n) = \Omega(g(n))$$ means that there is a constant $$c>0$$ such that, for every sufficiently large $$n$$, there is at least one input of size $$n$$ such that $$f_{Alg}(n) \ge c g(n)$$. With this interpretation you cannot say that an algorithm $$X$$ that takes $$2^n$$ time on inputs of even even length and $$n$$ time on inputs of odd length, has a time complexity of $$\Omega(2^n)$$.
That said, sometimes $$f_{Alg}(n) = \Omega(g(n))$$ is used in the following weaker sense: there is a constant $$c>0$$ such that, for every sufficiently large $$n$$, there is at least one input of size $$n' \ge n$$ such that $$f_{Alg}(n') \ge c g(n')$$. In this sense you would say that $$X$$ has time complexity of $$\Omega(2^n)$$.
Less commonly, $$f_{Alg}(n) = \Omega(g(n))$$ is used in the following stronger sense: for every sufficiently large $$n$$, and for every input of size $$n$$, $$f_{Alg}(n) \ge c g(n)$$. In this sense, $$f_A$$ as defined above would not even belong to $$\Omega(n^3)$$. This notion is not really useful, since it is often very easy to design algorithms for which the best lower-bound on their running time according to the above interpretation is $$\Omega(n)$$ (by checking if the input belongs to some class of inputs for which the solution is trivially known).