第二十三课 Asymtotic analysis-2

|-----------------------------------------------------------------------------|
| Omega(f(n)) is the set of all functions T(n) that satisfy:                  |
|                                                                             |
|   There exist positive constants d and N such that, for all n >= N,         |
|                              T(n) >= d f(n)                                 |
|-----------------------------------------------------------------------------|
^^^^^^^^^^  Compare with the definition of Big-Oh:  T(n) <= c f(n). ^^^^^^^^^^^

Omega is the reverse of Big-Oh. If T(n) is in O(f(n)), f(n) is in Omega(T(n)).

Big-Omega gives us a *LOWER BOUND* on a function, just as Big-Oh gives us an *UPPER BOUND* . Big-Oh says, "Your algorithm is at least this good." Big-Omega says, "Your algorithm is at least this bad."

Recall that Big-Oh notation can be misleading because, for instance, n is in O(n^8). If we know both a lower bound and an upper bound for a function, and they're both the same bound asymptotically (i.e. they differ only by a constant factor), we can use Big-Theta notation to precisely specify the function's asymptotic behavior.

|-----------------------------------------------------------------------------|
| Theta(f(n)) is the set of all functions that are in both of                 |
|                                                                             |
|                         O(f(n)) and Omega(f(n)).                            |
|-----------------------------------------------------------------------------|

But how can a function be sandwiched between f(n) and f(n)? Easy: we choose different constants (c and d) for the upper bound and lower bound. For instance, here is a function T(n) in Theta(n):

          c f(n) = 10 n
^                /
|               /                T(n)
|              /               **
|             /               *  *
|            /   ***          *   **
|           /   *   *         *
|   ***    /   *     *       *
| **   ** /    *     *       *
|*       **   *       *      *
*       /  *  *        **   *
|      /    **           ***     ~~~
|     /                     ~~~~~
|    /                 ~~~~~
|   /             ~~~~~
|  /         ~~~~~     d f(n) = 2 n
| /     ~~~~~
|/ ~~~~~
O~~------------------------------> n

If we extend this graph infinitely far to the right, and find that T(n) remains always sandwiched between 2n and 10n, then T(n) is in Theta(n). If T(n) is an algorithm's worst-case running time, the algorithm will never exhibit worse than linear performance, but it can't be counted on to exhibit better than linear performance, either.

Theta is symmetric: if f(n) is in Theta(g(n)), then g(n) is in Theta(f(n)). For instance, n^3 is in Theta(3 n^3 - n^2), and 3 n^3 - n^2 is in Theta(n^3). n^3 is not in Theta(n), and n is not in Theta(n^3).

Big-Theta notation isn't potentially misleading in the way Big-Oh notation can be: n is NOT in Omega(n^8). If your algorithm's running time is in Theta(n^8), it IS slow.

However, some functions are not in "Theta" of anything simple. For example, the function f(n) = n (1 + sin n) is in O(n) and Omega(0), but it's not in Theta(n) nor Theta(0). f(n) keeps oscillating back and forth between zero and ever-larger numbers. We could say that f(n) is in Theta(2n (1 + sin n)), but that's not a simplification.

Remember that the choice of O, Omega, or Theta is independent of whether we're talking about worst-case running time, best-case running time, average-case running time, memory use, annual beer consumption as a function of population, or some other function. The function has to be specified. "Big-Oh" is NOT a synonym for "worst-case running time," and Omega is not a synonym for "best-case running time."

There are p (p - 1) / 2 pairs, and each pair takes constant time to examine. Therefore, worst- and best-case running times are in Theta(p^2).

Often, you can figure out the running time of an algorithm just by looking at the loops–their loop bounds and how they are nested. For example, in the closest pair code below, the outer loop iterates p times, and the inner loop iterates an average of roughly p / 2 times, which multiply to Theta(p^2) time.

double minDistance = point[0].distance(point[1]);

/* Visit a pair (i, j) of points. */
for (int i = 0; i < numPoints; i++) {
  /* We require that j > i so that each pair is visited only once. */
  for (int j = i + 1; j < numPoints; j++) {
    double thisDistance = point[i].distance(point[j]);
    if (thisDistance < minDistance) {
      minDistance = thisDistance;
    }
  }
}

But doubly-nested loops don't always mean quadratic running time! The next example has the same loop structure, but runs in linear time.

int i = 0, j = 0;

while (i < ints.length) {
  ints[j] = ints[i];
  do {
    i++;
  } while ((i < ints.length) && (ints[i] == ints[j]));
  j++;
}
// Code to fill in -1's at end of array omitted.

The outer loop can iterate up to ints.length times, and so can the inner loop. But the index "i" advances on every iteration of the inner loop. It can't advance more than ints.length times before both loops end. So the worst-case running time of this algorithm is in Theta(ints.length). (So is the best-case time.)

Unfortunately, I can't give you a foolproof formula for determining the running time of any algorithm. You have to think! In fact, the problem of determining an algorithm's running time is, in general, as hard as proving any mathematical theorem. For instance, I could give you an algorithm whose running time depends on whether the Riemann Hypothesis (one of the greatest unsolved questions in mathematics) is true or false.