Limit Definition of Big-O,Big-$\mathrm{\Omega }$, Big-$\mathrm{\Theta }$

(Notice that multiple cases may be true.)

L’Hôpital’s Rule

If ${\displaystyle \underset{n\to \mathrm{\infty }}{lim}f(n)=\underset{n\to \mathrm{\infty }}{lim}g(n)=\mathrm{\infty }}$ and $f^{\prime }(n)$ and $g^{\prime }(n)$ exist, then

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=\underset{n\to \mathrm{\infty }}{lim}\frac{f^{\prime }(n)}{g^{\prime }(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 \underset{n\to \mathrm{\infty }}{lim}\frac{n^3+3n+2}{n^2}}$
  • $={\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{n^3}{n^2}+\frac{3n}{n^2}+\frac{2}{n^2}}$
  • $={\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{n}{1}+\frac{3}{n}+\frac{2}{n^2}}$
  • $={\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{n}{1}+\underset{n\to \mathrm{\infty }}{lim}\frac{3}{n}+\underset{n\to \mathrm{\infty }}{lim}\frac{2}{n^2}=\mathrm{\infty }+0+0=\mathrm{\infty }}$
  • $\therefore n^3+3n+2\in \mathrm{\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 \underset{n\to \mathrm{\infty }}{lim}\frac{n^3+3n+2}{n^2}}$
  • $={\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{3n^2+3}{2n}}$
  • $={\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{6n}{2}={\displaystyle \underset{n\to \mathrm{\infty }}{lim}3n=\mathrm{\infty }}}$
  • $\therefore n^3+3n+2\in \mathrm{\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}}$