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.

nbro
  • 15,395
  • 32
  • 113
  • 196
Suhail Gupta
  • 22,386
  • 64
  • 200
  • 328
  • @Ash Burlaczenko As I mentioned,I find that boring because I am not understanding it.I think it's obvious ! – Suhail Gupta Aug 27 '12 at 08:05
  • 2
    @Suhail your symbol doesn't show up in my browser.Edited – UmNyobe Aug 27 '12 at 08: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 '12 at 08: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 '12 at 08:49
  • @amit: It has nothing to do with the notation, but it has something to do with how people assign the complexity. My point is: the upper and lower bound of Selection Sort is the same (it is oblivious to the input), so we can say that the algorithm has Theta(n^2) complexity, while we can only say that the Insertion Sort algorithm is O(n^2), since it is always upper bounded by a quadratic function. – nhahtdh Aug 27 '12 at 10:16
  • 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 '12 at 10:24
  • @nhahtdh: I don't understand the question. There is no *correct* method to calculate analysis. It depends on your need. Sometimes worst case is most important (for example - real time apps, like missiles guidance systems), and sometimes you care for the average or even amortized case (usually when throughput is the main issue). Example: hash table insertion is `Theta(n)` worst case and `Theta(1)` average [assuming no rehashing is needed, for simplicty] – amit Aug 27 '12 at 10:39

5 Answers5

65

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.

mshwf
  • 7,009
  • 12
  • 59
  • 133
amit
  • 175,853
  • 27
  • 231
  • 333
  • `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_ ? – Suhail Gupta Aug 27 '12 at 09: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 '12 at 09: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 '12 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 '12 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. – Suhail Gupta Aug 27 '12 at 11:05
  • @SuhailGupta: What is that *specifically* that you don't understand? Do you understand what an "asymptotic bound" is? An [asymptote](http://en.wikipedia.org/wiki/Asymptote) in general? Please specify so where is your difficulty specifically, so I'll can try to focus on it. – amit Aug 27 '12 at 11:17
  • I do not get a feel of what each means. I understand what an asymptote is. I also understand the mathematical definitions of lower asymptotic bound and upper asymptotic bound – Suhail Gupta Aug 27 '12 at 11:22
  • Ok, good. Then a *function* is said to be `O(f(n))` if it has `f(n)` as upper asymptotic bound. it is `Omega(g(n))` if it has g(n) as lower asymptotic bound. Both refer to *functions*, not *algorithms*. To say an algorithm is big O (for example) is inaccurate, we need to say actually: The algorithm 'alg' is `O(f(n))` *under worst case analysis*. The worst case analysis gives us how many ops the algorithm does for each `n`, in the worst case - and thus a function. Is it clear so far? – amit Aug 27 '12 at 11:27
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/15845/discussion-between-suhail-gupta-and-amit) – Suhail Gupta Aug 27 '12 at 11:31
  • @amit can i consider this as an advantage if big-Theta is more informative than big-O notation? – NoobProgrammer Sep 14 '22 at 03:47
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.

jub0bs
  • 60,866
  • 25
  • 183
  • 186
rjha94
  • 4,292
  • 3
  • 30
  • 37
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)

VSOverFlow
  • 1,025
  • 8
  • 11
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.

sma
  • 9,449
  • 8
  • 51
  • 80
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.

faester
  • 14,886
  • 5
  • 45
  • 56