Plain English explanation of Theta notation?

Question

What is a plain English explanation of Theta notation? With as little formal definition as possible and simple mathematics.

How theta notation is different from the Big O notation ? Could anyone explain in plain English?

In algorithm analysis how there are used? I am confused?

Answer 1

If an algorithm's run time is Big Theta(f(n)), it is asymptotically bounded above and below by f(n). Big O is the same except that the bound is only above.

Intuitively, Big O(f(n)) says "we can be sure that, ignoring constant factors and terms, the run time never exceeds f(n)." In rough words, if you think of run time as "bad", then Big O is a worst case. Big Theta(f(n)) says "we can be sure that, ignoring constant factors and terms, the run time always varies as f(n)." In other words, Big Theta is a known tight bound: it's both worst case and best case.

A final try at intuition: Big O is "one-sided." O(n) run time is also O(n^2) and O(2^n). This is not true with Big Theta. If you have an algorithm run time that's O(n), then you already have a proof that it's not Big Theta(n^2). It may or may not be Big Theta(n)

An example is comparison sorting. Information theory tells us sorting requires at least ceiling(n log n) comparisons, and we have actually invented O(n log n) algorithms (where n is number of comparisons), so sorting comparisons are Big Theta(n log n).

Answer 2

I have always wanted to put this down in Simple words. Here is my try.

If an algorithm's time or space complexity is expressed in

• Big O : Ex O(n) - means n is the upper limit. Final Value could be less than or equal to n.

• Big Omega : Ex Ω(n) - means n is the lower limit. Final Value could be equal to or more than n.

• Theta : Ex Θ(n) - means n is the only possible value. (both upper limit & lower limit)