Limit Definition of Big-O

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

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=c<\mathrm{\infty }$$

where $c$ is some constant (possibly 0)

Limit Definition of Big-$\mathrm{\Omega }$

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

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=c>0$$

where $c$ is some constant (possibly $\mathrm{\infty }$)

Limit Definition of Big-$\mathrm{\Theta }$

$f(n)\in \mathrm{\Theta }(g(n))$ if

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=c,0<c<\mathrm{\infty }$$

where $c$ is some constant.

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}}$