Limit Definition of Big-O

\(f(n) \in O(g(n))\) if

\[\lim_{n \to \infty} \frac{f(n)}{g(n)} = c < \infty\]

where \(c\) is some constant (possibly 0)

Limit Definition of Big-\(\Omega\)

\(f(n) \in O(g(n))\) if

\[\lim_{n \to \infty} \frac{f(n)}{g(n)} = c > 0\]

where \(c\) is some constant (possibly \(\infty\))

Limit Definition of Big-\(\Theta\)

\(f(n) \in \Theta(g(n))\) if

\[\lim_{n \to \infty} \frac{f(n)}{g(n)} = c, \;\;\;0 < c < \infty\]

where \(c\) is some constant.

L’Hôpital’s Rule

If \(\displaystyle \lim_{n \to \infty} f(n) = \lim_{n \to \infty} g(n) = \infty\) and \(f'(n)\) and \(g'(n)\) exist, then

\[\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{f'(n)}{g'(n)}\]

Applying Limit Definitions

The limit definitions often provide the easiest way to formally demonstrate the asymptotic relationship between two functions…

Using algebra and basic limit rules:

• \(n^3 + 3n + 2 \stackrel{?}{\in} O(n^2)\)
  • \(\displaystyle \lim_{n \to \infty} \frac{n^3 + 3n + 2}{n^2}\)
  • \(= \displaystyle \lim_{n \to \infty} \frac{n^3}{n^2} + \frac{3n}{n^2} + \frac{2}{n^2}\)
  • \(= \displaystyle \lim_{n \to \infty} \frac{n}{1} + \frac{3}{n} + \frac{2}{n^2}\)
  • \(= \displaystyle \lim_{n \to \infty} \frac{n}{1} + \lim_{n \to \infty} \frac{3}{n} + \lim_{n \to \infty} \frac{2}{n^2}= \infty + 0 + 0 = \infty\)
  • \(\therefore n^3 + 3n + 2 \in \Omega(n^2)\)

Applying Limit Definitions

The limit definitions often provide the easiest way to formally demonstrate the asymptotic relationship between two functions…

Using L’Hôpital’s rule

• \(n^3 + 3n + 2 \stackrel{?}{\in} O(n^2)\)
  • \(\displaystyle \lim_{n \to \infty} \frac{n^3 + 3n + 2}{n^2}\)
  • \(=\displaystyle \lim_{n \to \infty} \frac{3n^2 + 3}{2n}\)
  • \(=\displaystyle \lim_{n \to \infty} \frac{6n}{2} =\displaystyle \lim_{n \to \infty} 3n = \infty\)
  • \(\therefore n^3 + 3n + 2 \in \Omega(n^2)\)

Average Case Analysis

public static boolean contains(int target, int[] numbers) {
  for (int number : numbers) {
    if (number == target) {
      return true;
    }
  }
  return false;
}

• Best Case: \(1\) comparison, \(O(1)\)
• Worst Case: \(n\) comparisons, \(O(n)\)
• Average Case: ???
  • Determine the distribution to average over (do we assume that the item is in the collection? 50% likely to be in the collection?)
  • Sum over the cost of all possible outcomes, and divide by the number of outcomes.
  • \(\displaystyle \frac{1 + 2 + ... + n}{n} = \frac{\sum_{i=1}^n i}{n} = \frac{n(n+1)/2}{n} = \frac{n+1}{2}\)