51

While trying to understand the difference between Theta and O notation I came across the following statement :

The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.

But I do not understand this. The book explains it mathematically, but it's too complex and gets really boring to read when I am really not understanding.

Can anyone explain the difference between the two using simple, yet powerful examples.

7
  • @Ash Burlaczenko As I mentioned,I find that boring because I am not understanding it.I think it's obvious ! Aug 27, 2012 at 8:05
  • 2
    @Suhail your symbol doesn't show up in my browser.Edited
    – UmNyobe
    Aug 27, 2012 at 8:06
  • Another example is Insertion Sort vs. Selection Sort. They are both O(n^2) in worst case, but in best case, Insertion Sort performs at O(n), while Selection Sort is O(n^2) for all cases. We will say that Insertion Sort is O(n^2), and Selection Sort is Theta(n^2) (lower bound = upper bound).
    – nhahtdh
    Aug 27, 2012 at 8:23
  • 2
    @nhahtdh: Your example is misleading. best case and worst case have nothing to do with big O/Theta notation. These (big O/Theta) are mathematical sets that include functions. An algorithm is not said to be Theta(f(n)) if the worst case and best case are identical, we say it is Theta(f(n)) worst case (for example), if the worst case is both O(f(n)) and Omega(f(n)), regardless of the behavior of the best case.
    – amit
    Aug 27, 2012 at 8:49
  • 1
    @nhahtdh: This is wrong. The worst case of insertion sort is Theta(n^2), since you can give a lower bound on how many ops will be needed on a worst case input (reversed order array), and it will be quadric in the number of elements. There is no sense talking about complexity of an algorithm without indicating under what analyzis it is calculated. Usually when the analyzis is omitted - it implicitly means that the complexity is calculated under the worst case analyzis. If we use this convention, insertion sort is Theta(n^2) [worst case analyzis is implicit in this claim].
    – amit
    Aug 27, 2012 at 10:24

5 Answers 5

64

Big O is giving only upper asymptotic bound, while big Theta is also giving a lower bound.

Everything that is Theta(f(n)) is also O(f(n)), but not the other way around.
T(n) is said to be Theta(f(n)), if it is both O(f(n)) and Omega(f(n))

For this reason big-Theta is more informative than big-O notation, so if we can say something is big-Theta, it's usually preferred. However, it is harder to prove something is big Theta, than to prove it is big-O.

For example, merge sort is both O(n*log(n)) and Theta(n*log(n)), but it is also O(n2), since n2 is asymptotically "bigger" than it. However, it is NOT Theta(n2), Since the algorithm is NOT Omega(n2).


Omega(n) is asymptotic lower bound. If T(n) is Omega(f(n)), it means that from a certain n0, there is a constant C1 such that T(n) >= C1 * f(n). Whereas big-O says there is a constant C2 such that T(n) <= C2 * f(n)).

All three (Omega, O, Theta) give only asymptotic information ("for large input"):

  • Big O gives upper bound
  • Big Omega gives lower bound and
  • Big Theta gives both lower and upper bounds

Note that this notation is not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.

10
  • f(n) is theta g(n) when "f(n) is O(n) and f(n) is omega(n)". I understand that omega(n) tells me the worst case (is that so ?) and O(n) tells me the behavior of the function with some large inputs, against the time. What does theta(n) depict / tell ? Aug 27, 2012 at 9:20
  • 1
    @SuhailGupta: Omega(n) is assymptotic lower bound. If T(n) is Omega(f(n)), it means that from a certain n0, there is a constant C such as, T(n) >= C * f(n) (Where big-O says there is a constant C2 such that T(n) <= C2 * f(n))). All three (Omega,O,Theta) gives only asymptotic information ("for large input"), Big O gives upper bound, big Omega gives lower bound, and big Theta gives both. Note that this notation is NOT related to the best/worst/average case analyzis of algorithms. Each one of these can be applied to each analyzis.
    – amit
    Aug 27, 2012 at 9:51
  • I'm quite sure that I'm clear about what the notations mean (in mathematical sense). But when you mention it (and when I read some article on Wikipedia about sorting), I'm a bit confused as to how the notations are used in worse/best/avg case analysis: Why they assign theta notation in the case of Cycle sort, but they use O notation for the case of Selection sort.
    – nhahtdh
    Aug 27, 2012 at 10:24
  • 1
    @nhahtdh: The authors of these articles might be unsure themselves. (Remember wikipedia is not always editted by professional CS, could be an article created/editted by a confused UG student). Note that big O/Theta/Omega are classes of functions, and not algorithms. (worst/best/average/.. case analyzis is actually a function that converts an algorithm to a function). Also note: it is not wrong to claim a Theta(n^2) function is O(n^2) - thus the wikipedia claims - though not accurate - are not wrong.
    – amit
    Aug 27, 2012 at 10:31
  • I have a algorithm 'Alg' for which omega, theta, big O are defined. Explain me in very simple language what will each of them tell me about the algorithm 'Alg'? Use an alias for lower bound or upper bound or explain them. Aug 27, 2012 at 11:05
11

I will just quote from Knuth's TAOCP Volume 1 - page 110 (I have the Indian edition). I recommend reading pages 107-110 (section 1.2.11 Asymptotic representations)

People often confuse O-notation by assuming that it gives an exact order of Growth; they use it as if it specifies a lower bound as well as an upper bound. For example, an algorithm might be called inefficient because its running time is O(n^2). But a running time of O(n^2) does not necessarily mean that running time is not also O(n)

On page 107,

1^2 + 2^2 + 3^2 + ... + n^2 = O(n^4) and

1^2 + 2^2 + 3^2 + ... + n^2 = O(n^3) and

1^2 + 2^2 + 3^2 + ... + n^2 = (1/3) n^3 + O(n^2)

Big-Oh is for approximations. It allows you to replace ~ with an equals = sign. In the example above, for very large n, we can be sure that the quantity will stay below n^4 and n^3 and (1/3)n^3 + n^2 [and not simply n^2]

Big Omega is for lower bounds - An algorithm with Omega(n^2) will not be as efficient as one with O(N logN) for large N. However, we do not know at what values of N (in that sense we know approximately)

Big Theta is for exact order of Growth, both lower and upper bound.

5

I am going to use an example to illustrate the difference.

Let the function f(n) be defined as

if n is odd f(n) = n^3
if n is even f(n) = n^2

From CLRS

A function f(n) belongs to the set Θ(g(n)) if there exist positive constants c1 and c2 such that it can be "sandwiched" between c1g(n) and c2g(n), for sufficiently large n.

AND

O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.

AND

Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.

The upper bound on f(n) is n^3. So our function f(n) is clearly O(n^3).

But is it Θ(n^3)?

For f(n) to be in Θ(n^3) it has to be sandwiched between two functions one forming the lower bound, and the other the upper bound, both of which grown at n^3. While the upper bound is obvious, the lower bound can not be n^3. The lower bound is in fact n^2; f(n) is Ω(n^2)

From CLRS

For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

Hence f(n) is not in Θ(n^3) while it is in O(n^3) and Ω(n^2)

5

If the running time is expressed in big-O notation, you know that the running time will not be slower than the given expression. It expresses the worst-case scenario.

But with Theta notation you also known that it will not be faster. That is, there is no best-case scenario where the algorithm will retun faster.

This gives are more exact bound on the expected running time. However for most purposes it is simpler to ignore the lower bound (the possibility of faster execution), while you are generally only concerned about the worst-case scenario.

5

Here's my attempt:

A function, f(n) is O(n), if and only if there exists a constant, c, such that f(n) <= c*g(n).

Using this definition, could we say that the function f(2^(n+1)) is O(2^n)?

  1. In other words, does a constant 'c' exist such that 2^(n+1) <= c*(2^n)? Note the second function (2^n) is the function after the Big O in the above problem. This confused me at first.

  2. So, then use your basic algebra skills to simplify that equation. 2^(n+1) breaks down to 2 * 2^n. Doing so, we're left with:

    2 * 2^n <= c(2^n)

  3. Now its easy, the equation holds for any value of c where c >= 2. So, yes, we can say that f(2^(n+1)) is O(2^n).

Big Omega works the same way, except it evaluates f(n) >= c*g(n) for some constant 'c'.

So, simplifying the above functions the same way, we're left with (note the >= now):

2 * 2^n >= c(2^n)

So, the equation works for the range 0 <= c <= 2. So, we can say that f(2^(n+1)) is Big Omega of (2^n).

Now, since BOTH of those hold, we can say the function is Big Theta (2^n). If one of them wouldn't work for a constant of 'c', then its not Big Theta.

The above example was taken from the Algorithm Design Manual by Skiena, which is a fantastic book.

Hope that helps. This really is a hard concept to simplify. Don't get hung up so much on what 'c' is, just break it down into simpler terms and use your basic algebra skills.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.