Order Notation#

We will not get too formal in our discussion of order notation as that is best left to a textbook wholly on algorithm design. There are three main kinds of order notation:

  1. Using \(\theta\), e.g. \(\theta (f(n)) \) , and said as “theta of \(f(n)\)”.
    This is a set that holds all functions that grow in a similar manner. The functions in the set can all be bounded from both the top by \(cf(n)\) and bottom by \(kf(n)\), for some constants \(c \neq 0 \), and \(k \neq 0\), and \(n\) sufficiently big.

  2. Using \(O\), e.g. \(O(f(n))\) , and said as “Big Oh of \(f(n)\)”.
    This is a set that holds all functions that grow in a similar manner or slower. The functions in the set can all be bounded from the top by \(cf(n)\), for some constant \(c \neq 0 \), and \(n\) sufficiently big.

  3. Using \(\Omega\), e.g. \(\Omega(f(n))\) , and said as “omega of \(f(n)\)”.
    This is a set that holds all functions that grow in a similar manner or faster. The functions in the set can all be bounded from the bottom by \(kf(n)\), for some constant \(k \neq 0 \), and \(n\) sufficiently big.

You won’t get many bragging rights for your code if you say it is in \(\Omega\) of anything. What does it mean?

My code runs in \(\Omega(1)\)

Your algorithm runs in constant time, or worse. Big deal. So does every algorithm we know about.

On the other hand, Big Oh does come with bragging rights.

My code runs in \(O(n^2)\)

Now this means something. We know that your algorithm runs in a time that is quadratic or perhaps even better.

If you know the upper and lower bounds on your algorithm’s run-time, and if they match, then you should use theta notation.

My code runs in \(\theta (n^2)\)

Now we know your algorithm runs in quadratic time, not better and not worse.

Order of \(f(n)\)#

Computing Scientists get lax with their notation, and have another phrase “order of \(f(n)\)”. Though this order is written with a Big Oh, it can either mean Big Oh or theta, never omega. The interpretation of \(O(f(n))\) = “order of \(f(n)\)” must be taken in context, carefully.

Practice Questions#

  1. Which of the following functions are in \(\Omega (n)\):
    a. \(10\)
    b. \(n \log n\)
    c. \(n\)
    d. \(100n + 52,000\)
    e. \(92n^2 + 4\)
    f. \(1,000,000 \log n + 89\)
    g. \(3^n + 1\)

  2. Which of the following are in \(O(n^2)\):
    a. \(1\)
    b. \(n \log n\)
    c. \(2n^3 + 13\)
    d. \(100n + 52,000\)
    e. \(92n^2 + 4n + 4\)
    f. \(1,000,000 \log n + 89\)
    g. \(3^n + 1\)

  3. Which of the following are in \(\theta (\log n)\):
    a. \(41\)
    b. \(n \log n\)
    c. \(n\)
    d. \(199 \log n + 5,000\)
    e. \(2^n \log n + 4\)
    f. \(1,000,000 \log n + 2n + 89\)
    g. \(3^n + 1\)

To Solutions