Why doesn't small theta asymtotic notation exist?

Question

This question was asked by our professor and I didn't understand why small theta doesn't exists/ I think I understand this, but how can we mathematically prove that it doesn't exists.

Answer 1

Definitions:

Big O: Upper bound on an algorithm's runtime.

Big Theta (Θ): This is a "tight" or "exact" bound. It is a combination of Big O and Big Omega.

Big Omega (Ω): Lower bound on an algorithm's runtime.

Little o: Upper bound on an algorithm's runtime but the asymptotic runtime cannot equal the upper bound.

Little Omega (ω): Lower bound on an algorithm's runtime but the asymptotic runtime cannot equal the lower bound.

Think of It Like This

o(n) = O(n) - Θ(n) (we can't "touch" the upper bound)
ω(n) = Ω(n) - Θ(n) (we can't "touch" the lower bound)

If We Did The Same

θ(n) = Θ(n) - Θ(n)

We would basically be saying that the runtime cannot touch the exact bound we set for it...which is impossible since it is an exact bound. The runtime is definitely going to "touch" it.

How can we mathematically prove that it doesn't exist

There are no runtimes that the algorithm could take on that would not intersect with an exact bound. So the set of all runtimes belonging to a theoretical little theta would be the empty set.