If algorithm time complexity is theta(n^2), is it possible that for one input it will run in O(n)?

Question

If algorithm time complexity is theta(n^2), is it possible that for one input it will run in O(n)? by the definition of theta it seems to be that no input will run in O(n). however some say that its possible.

I really can't think of a scenario that an algorithm that run in theta(n^2), will have one input that may run in O(n).

If its true, can you please explain to me and give me an example?

Thanks a lot!

Answer 1

I think your terminology is tripping you up.

An algorithm cannot be "Θ(n²)." Theta notation describes the growth rates of functions. You can say that an algorithm's runtime is Θ(n²), in which case the algorithm cannot run in time O(n) on any inputs, or you could say that an algorithm's worst-case runtime is Θ(n²), in which case it could conceivably be possible that the algorithm will run in time O(n) for some inputs (take, for example, insertion sort).

Hope this helps!

Answer 2

If algorithm time complexity is theta(n^2), is it possible that for one input it will run in O(n)?

No. Here's why. Lets say that the running time of your algorithm is f(n). Since f(n) = Θ(n) then we'll have for some constants c0>0 and n0>0 such that c0*n^2 <= f(n) for every n >= n0. Lets us suppose that f(n) = O(n). This would mean that for some constants c1>0, n1>0 we would have f(n) <= c1*n for every n>=n1. Then for n >= max(n1, n2) we would have c0*n^2 <= f(n) <= c1*n => c0*n <= c1 which is not true for n > c1/c0. Contradiction.

Informally, you can always think of O as <= and Θ as = (and of Ω as >=). So you can reformulate your problem as:

if something is equal to n^2 is it less than n?