What exactly does big Ө notation represent?

 

I'm really confused about the differences between big O, big Omega, and big Theta notation.

I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (theta) represent?

I have read that it means tight bound , but what does that mean?

It means that the algorithm is both big-O and big-Omega in the given function.

For example, if it is Ө(n) , then there is some constant k , such that your function (run-time, whatever), is larger than n*k for sufficiently large n , and some other constant K such that your function is smaller than n*K for sufficiently large n .

In other words, for sufficiently large n , it is sandwiched between two linear functions :

For k < K and n sufficiently large, n*k < f(n) < n*K

First let's understand what big O, big Theta and big Omega are. They are all sets of functions.

Big O is giving upper asymptotic bound, while big Omega is giving a lower bound. Big Theta gives both.

Everything that is Ө(f(n)) is also O(f(n)) , but not the other way around.
T(n) is said to be in Ө(f(n)) if it is both in O(f(n)) and in Omega(f(n)) .
In sets terminology, Ө(f(n)) is the intersection of O(f(n)) and Omega(f(n))

For example, merge sort worst case is both O(n*log(n)) and Omega(n*log(n)) - and thus is also Ө(n*log(n)) , but it is also O(n^2) , since n^2 is asymptotically "bigger" than it. However, it is not Ө(n^2) , Since the algorithm is not Omega(n^2) .

A bit deeper mathematic explanation

O(n) is asymptotic upper bound. If T(n) is O(f(n)) , it means that from a certain n0 , there is a constant C such that T(n) <= C * f(n) . On the other hand, big-Omega says there is a constant C2 such that T(n) >= C2 * f(n)) ).

Do not confuse!

Not to be confused with worst, best and average cases analysis: all three (Omega, O, Theta) notation are not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.

We usually use it to analyze complexity of algorithms (like the merge sort example above). When we say "Algorithm A is O(f(n)) ", what we really mean is "The algorithms complexity under the worst1 case analysis is O(f(n)) " - meaning - it scales "similar" (or formally, not worse than) the function f(n) .

Why we care for the asymptotic bound of an algorithm?

Well, there are many reasons for it, but I believe the most important of them are:

  • It is much harder to determine the exact complexity function, thus we "compromise" on the big-O/big-Theta notations, which are informative enough theoretically.
  • The exact number of ops is also platform dependent. For example, if we have a vector (list) of 16 numbers. How much ops will it take? The answer is: it depends. Some CPUs allow vector additions, while other don't, so the answer varies between different implementations and different machines, which is an undesired property. The big-O notation however is much more constant between machines and implementations.

    • To demonstrate this issue, have a look at the following graphs: 在这里输入图像描述

    It is clear that f(n) = 2*n is "worse" than f(n) = n . But the difference is not quite as drastic as it is from the other function. We can see that f(n)=logn quickly getting much lower than the other functions, and f(n) = n^2 is quickly getting much higher than the others.
    So - because of the reasons above, we "ignore" the constant factors (2* in the graphs example), and take only the big-O notation.

    In the above example, f(n)=n, f(n)=2*n will both be in O(n) and in Omega(n) - and thus will also be in Theta(n) .
    On the other hand - f(n)=logn will be in O(n) (it is "better" than f(n)=n ), but will NOT be in Omega(n) - and thus will also NOT be in Theta(n) .
    Symetrically, f(n)=n^2 will be in Omega(n) , but NOT in O(n) , and thus - is also NOT Theta(n) .

    1Usually, though not always. when the analysis class (worst, average and best) is missing, we really mean the worst case.

    To answer you question, Asymptotic notation and Functions in Asymptotic notation also need to be explained. If you have patience to read it all, things will be very clear in the end.

    1. Asymptotic notation

    To think about algorithms you can use 2 main ideas:

  • Determine how long the algorithm takes in terms of its input.
  • Focus on how fast a function grows with the input size; aka rate of growth of the running time. Example: suppose that an algorithm, running on an input of size n, takes 6n^2 + 100n + 300 machine instructions. The 6n^2​​ term becomes larger than the remaining terms, 100 n + 300, once n becomes large enough, 20 in this case. 在这里输入图像描述

    • We would say that the running time of this algorithm grows as n^2​, dropping the coefficient 6 and the remaining terms 100n + 300. It doesn't really matter what coefficients we use; as long as the running time is an^2 + bn + c, for some numbers a > 0, b, and c, there will always be a value of n for which an^2 is greater than bn + c, and this difference increases as n increases. By dropping the constant coefficients and the less significant terms, we use asymptotic notation.

    2. Big-Theta

    Here's a simple implementation of linear search 

    var doLinearSearch = function(array) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};
  • Each of these little computations takes a constant amount of time each time it executes. If the for-loop iterates n times, then the time for all n iterations is c1 * n, where c​1​​ is the sum of the times for the computations in one loop iteration. This code has a little bit of extra overhead, for setting up the for-loop (including initializing guess to 0) and possibly returning -1 at the end. Let's call the time for this overhead c​2​​, which is also a constant. Therefore, the total time for linear search in the worst case is c​1​​*n+c​2​​.
  • the constant factor c​1​​ and the low-order term c​2​​ don't tell us about the rate of growth of the running time. What's significant is that the worst-case running time of linear search grows like the array size n. The notation we use for this running time is Θ(n). That's the Greek letter "theta," and we say "big-Theta of n" or just "Theta of n."

  • When we say that a particular running time is Θ(n), we're saying that once n gets large enough, the running time is at least k​1​​*n and at most k​2​​*n for some constants k​1​​ and k​2​​. Here's how to think of Θ(n) 在这里输入图像描述

  • For small values of n, we don't care how the running time compares with k​1​​*n or k​2​​*n. But once n gets large enough—on or to the right of the dashed line—the running time must be sandwiched between k​1​​*n and k​2​​*n. As long as these constants k​1​​ and k​2​​ exist, we say that the running time is Θ(n).

  • When we use big-Θ notation, we're saying that we have an asymptotically tight bound on the running time. "Asymptotically" because it matters for only large values of n. "Tight bound" because we've nailed the running time to within a constant factor above and below.

    • 3. Functions in asymptotic notation

  • Suppose that an algorithm took a constant amount of time, regardless of the input size. For example, if you were given an array that is already sorted into increasing order and you had to find the minimum element, it would take constant time, since the minimum element must be at index 0. Since we like to use a function of n in asymptotic notation, you could say that this algorithm runs in Θ(n^​0) time. Why? Because n^0 = 1, and the algorithm's running time is within some constant factor of 1. In practice, we don't write Θ(n​^0​​), however; we write Θ(1)
  • Here's a list of functions in asymptotic notation that we often encounter when analyzing algorithms, listed from slowest to fastest growing. This list is not exhaustive; there are many algorithms whose running times do not appear here:
  • Θ(1) (aka constant search)
  • Θ(lg n) (aka binary search)
  • Θ(n) (aka linear search)
  • Θ(n*lg n)
  • Θ(n​^2​​)
  • Θ(n^​2*​​lg n)
  • Θ(n​^3​​)

  • Θ(2​^n​​)

  • Note that an exponential function a^n​​, where a > 1, grows faster than any polynomial function n^b​​, where b is any constant.

    • 4. Big-O notation

  • We use big-Θ notation to asymptotically bound the growth of a running time to within constant factors above and below. Sometimes we want to bound from only above. It would be convenient to have a form of asymptotic notation that means "the running time grows at most this much, but it could grow more slowly." We use "big-O" notation for just such occasions.
  • If a running time is O(f(n)), then for large enough n, the running time is at most k*f(n) for some constant k. Here's how to think of a running time that is O(f(n)): 在这里输入图像描述
  • If you go back to the definition of big-Θ notation, you'll notice that it looks a lot like big-O notation, except that big-Θ notation bounds the running from both above and below, rather than just from above. If we say that a running time is Θ(f(n)) in a particular situation, then it's also O(f(n)). For example, we can say that because the worst-case running time of binary search is Θ(lg n), it's also O(lg n). The converse is not necessarily true: as we've seen, we can say that binary search always runs in O(lg n) time but not that it always runs in Θ(lg n) time.
  • Suppose you have 10 dollars in your pocket. You go up to your friend and say, "I have an amount of money in my pocket, and I guarantee that it's no more than one million dollars." Your statement is absolutely true, though not terribly precise. One million dollars is an upper bound on 10 dollars, just as O(n) is an upper bound on the running time of binary search.
  • Other, imprecise, upper bounds on binary search would be O(n^2), O(n^3), and O(2^n). But none of Θ(n),Θ(n^2​​),Θ(n​^3​​), andΘ(2^n​​) would be correct to describe the running time of binary search in any case.

    • 5. Big-Ω (Big-Omega) notation

  • Sometimes, we want to say that an algorithm takes at least a certain amount of time, without providing an upper bound. We use big-Ω notation; that's the Greek letter "omega."
  • If a running time is Ω(f(n)), then for large enough n, the running time is at least k*f(n) for some constant k. Here's how to think of a running time that is Ω(f(n)): 在这里输入图像描述
  • We say that the running time is "big-Ω of f(n)." We use big-Ω notation for asymptotic lower bounds, since it bounds the growth of the running time from below for large enough input sizes.
  • Just as Θ(f(n)) automatically implies O(f(n)), it also automatically implies Ω(f(n)). So we can say that the worst-case running time of binary search is Ω(lg n). We can also make correct, but imprecise, statements using big-Ω notation. For example, just as if you really do have a million dollars in your pocket, you can truthfully say "I have an amount of money in my pocket, and it's at least 10 dollars," you can also say that the worst-case running time of binary search is Ω(1), because it takes at least constant time.

    • Reference: https://www.khanacademy.org

    链接地址: http://www.djcxy.com/p/6796.html

    上一篇: 完成问题也是NP

    下一篇: 大Ө符号代表什么？