5

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?

kTiwari
  • 1,488
  • 1
  • 14
  • 21
  • 4
    As funny as it sounds, the answers for [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) actually describe big-Theta – amit Sep 08 '12 at 17:20
  • this is not big o ,this is the theta notation ... which can be sandwiched between two functions. – kTiwari Sep 08 '12 at 17:22
  • Also: Your first question (difference between big O and big Theta) is covered in the thread: [Difference between Big-Theta and Big O notation in simple language](http://stackoverflow.com/questions/12138212/difference-between-big-theta-and-big-o-notation-in-simple-language) – amit Sep 08 '12 at 18:32
  • See [How does one know which notation of time complexity analysis to use?](http://cs.stackexchange.com/questions/57/how-does-one-know-which-notation-of-time-complexity-analysis-to-use) on [cs.se] – Gilles 'SO- stop being evil' Sep 12 '12 at 12:10

2 Answers2

6

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

Gene
  • 46,253
  • 4
  • 58
  • 96
  • 3
    Man, if you're going to do computer science, you have to learn the words and math of computer science. There is no way around it. – Gene Sep 08 '12 at 17:48
  • 1
    Just for clearing some semantic issues: Note that an algorithm is not Big Theta nor big O of anything. `O(f(n))` and `Theta(f(n))` are sets of *functions*. The complexity (under some specific analysis) of an algorithm (which is a function) could be `O(f(n))` or `Theta(f(n))`. Also, sorting is not `Theta(nlogn)`. QuickSort average case (or merge sort worst case) are `Theta(nlogn)`. (Bubble sort on the other hand has a worst case complexity of `Theta(n^2)`, even though it is a sorting algorithm). – amit Sep 08 '12 at 18:26
  • @amit: i am totally confused ,sometimes certain author have taken big O for worst case ,and some author have taken big theta for worst case for the different algo. – kTiwari Sep 08 '12 at 18:52
  • 1
    @krishnaChandra: Big O and Big Theta can both be applied to *worst case*,*average case*, *best case*, or any other case you can think of. It is a used to bound the function, and not the algorithm. The worst case (for example) is producing a funciton (which is different from the average case usually), and each notation can be applied on any case. – amit Sep 08 '12 at 18:56
  • @amit: if any of the notation can be applied to any analysis then why there are there three notations ,why not a single one. – kTiwari Sep 08 '12 at 19:07
  • @krishnaChandra: Each notation gives something else. Did you look at this thread: [Difference between Big-Theta and Big O notation in simple language](http://stackoverflow.com/questions/12138212/difference-between-big-theta-and-big-o-notation-in-simple-language)? [This thread](http://stackoverflow.com/questions/7628991/upper-bound-vs-lower-bound-for-worst-case-running-time-of-an-algorithm) can also be helpful. – amit Sep 08 '12 at 19:14
  • @amit: ya gone through that ,but couldn't able to clear my point – kTiwari Sep 08 '12 at 19:17
  • @amit, so Big O and Big Omega are sets of only one function, right? – PaulD Apr 28 '14 at 11:23
  • @JesusChrist I am not sure I am following you. I tried to give a broad explanation in [this thread](http://stackoverflow.com/a/12338937/572670) some time ago, have a look - I hope it will clear some of your questions. Will be happy to answer if something is still unclear. – amit Apr 28 '14 at 15:45
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)

Kaleid-o-scope
  • 159
  • 2
  • 7