CODEWITHSUNDEEP
algorithmcomputer-sciencecomplexity-theorynotation
kTiwari
kTiwari

Reputation: 1508

Plain English explanation of Theta notation?

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?

Upvotes: 5

Views: 2788

Answers (2)

Kaleid-o-scope
Kaleid-o-scope

Reputation: 159

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)

Upvotes: 2

Gene
Gene

Reputation: 46960

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).

Upvotes: 6

Related Questions