Algorithm Analysis Fundamentals

Types of Analysis

Theoretical vs Empirical Analysis

1. Theoretical Analysis

Time efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size (n).

Basic Operation: The operation that contributes most towards the running time of the algorithm.

\boxed{ \text{Running Time: } T ( n ) \approx c_{op} C(n) } \\ \small \textit{where $T$ is running time,} \\ \textit{$n$ is input size,} \\ \textit{$c$ is execution time for basic operation, and} \\ \textit{$C$ is \# of times basic operation is executed} \\

In short, we care about:

  1. How long the basic operation takes, and
  2. How many times we do it.
Example: Input size & basic operation of some common problems
ProblemInput Size MeasureBasic Operation
Searching for key in a list of n items# of list’s items (n)Key comparison
Multiplying two matricesMatrix dimensions or total # of elementsMultiplication of two numbers
Checking if a given integer n is primen’size = # of digits (in binary representation)Division
Typical graph problem# of vertices and/or edgesVisiting a vertex or traversing an edge

2. Empirical Analysis

  1. Select a specific (typical) sample of inputs.
  2. Use a:
    1. Physical unit of time (e.g., ms), or
    2. Count # of basic operation executions
  3. Analyze empirical data.

Remember: The size and format of input may impact the time efficiency of an algorithm.

Best/Average/Worst Case

Some algorithms’ efficiency depends on form of input.

\boxed{ \text{Worst Case: } C_{\text{worst}}(n) - \text{max over inputs of size $n$} } \\~\\ \boxed{ \text{Best Case: } C_{\text{best}}(n) - \text{min over inputs of size $n$} } \\~\\ \boxed{ \text{Average Case: } C_{\text{avg}}(n) - \text{avg over inputs of size $n$} }

Remember: The average case is NOT the average of the worst and best case!

Example: Worst and Best Case of Sequential Search

Q: Find the worst and best case of this sequential search algorithm.

ALGORITHM SequentialSearch(A[0..n-1],k)
  // Searches for given value in given array
  // Input: Array (A) and search key (k)
  // Output: Index of first element that matches K, or -1 if no matches
  i \leftarrow 0
  while i \lt n and A[i] \ne K do
      i \leftarrow i \text{$+$} 1
  if i \lt n return i
  else return -1

A:

Example: Average Case of Sequential Search

Q: Find the worst and best case of this sequential search algorithm.

ALGORITHM SequentialSearch(A[0..n-1],k)
  // Searches for given value in given array
  // Input: Array (A) and search key (k)
  // Output: Index of first element that matches K, or -1 if no matches
  i \leftarrow 0
  while i \lt n and A[i] \ne K do
      i \leftarrow i \text{$+$} 1
  if i \lt n return i
  else return -1

A:

Standard Assumptions

  1. Let p be the probability of a successful search.
  1. For every i, the probability of first match occurring in the ith index is the same.

Cases

Case 1

In the case of a successful search, the probability of the first match occurring in the ith position of the list is p/n for every i,

Case 2

In the case of an unsuccessful search, the number of comparisons will be n with the probability of such a search being (1-p)

Thus, the total expected comparisons is simply the addition of the above two expectations:

C_{\text{avg}}(n) = \textcolor{green}{ \left[ 1 \times \frac{p}{n} + 2 \times \frac{p}{n} + ... + i \times \frac{p}{n} + ... + n \times \frac{p}{n} \right] } + \textcolor{red}{ n (1-p) } \\~\\ \small\textit{Left term (green): Case 1; Right term (red): Case 2}

Simplifying

Now, we can simplify:

\begin{aligned} C_{\text{avg}}(n) &= [ 1 \times \frac{p}{n} + 2 \times \frac{p}{n} + ... + i \times \frac{p}{n} + ... + n \times \frac{p}{n} ] + n (1-p) \\ &= \frac{p}{n} [ 1 + 2 + ... + i + ... + n ] + n(1-p) \\ &= \frac{p}{n} \frac{n(n+1)}{2} + n(1-p) \\ &= \frac{p(n+1)}{2} + n(1-p) \end{aligned}

Therefore, the average case is:

C_\text{avg}(n) = \frac{p(n+1)}{2} + n(1-p)

Amortized Analysis

Sometimes it’s better to analyze multiple runs rather than a single run.

Etymology: Amortization is from finance

Asymptotic Analysis

Order of Growth

Asymptotic Analysis: Analysis of order of growth.

Definition: Asymptotic

Asymptotic: The nature of a graph/function as it reaches large values.

Order of Growth: The dominant behavior of an algorithm as n \to \infin.

Example: Normal questions that about order of growth
Example: Values of some important functions as $n \to \infin$
nlog_2 nnn log_2 nn^2n^32^nn!
10^13.310^13.3 \times 10^110^210^310^33.6 \times 10^6
10^26.610^26.6 \times 10^210^410^61.3 \times 10^{30}9.3 \times 10^{157}
10^31010^31.0 \times 10^410^610^9
10^41310^41.3 \times 10^510^810^{12}
10^51710^51.7 \times 10^610^{10}10^{15}
10^62010^62.0 \times 10^710^{12}10^{18}

Why?: Looking at the asymptotic order of growth lets us compare functions by ignoring constant factors and small input sizes.

Bounds