http://imgs.xkcd.com/comics/efficiency.png

Summation Review

$\sum_{i=0}^{n}i = \sum_{i=1}^{n}i = 1 + 2 + ... + n = \frac{n(n+1)}{2}$

Proof:
$S = 1 + 2 + ... + (n-1) + n$
$S = n + (n-1) + ... + 2 + 1$
$2S = (n+1) + (n+1) + ... + (n+1) + (n+1)$
$2S = n(n+1)$
$S = \frac{n(n+1)}{2}$

---

$\sum_{i=l}^{u}ca_i = c \sum_{i=l}^{u}a_i$

Proof:
$\sum_{i=l}^{u}ca_i = ca_l + ca_{l+1} + ... + ca_n$
$= c(a_l + a_{l+1} + ... + a_n)$
$= c\sum_{i=l}^{u}a_i$

---

$\sum_{i+l}^{u}(a_i \pm b_i) = \sum_{i=l}^{u}a_i \pm \sum_{i=l}^{u}b_i$

---

$\sum_{i=l}^{u}1 = u - l + 1$

---

$\sum_{i=1}^{n}(a_i-a_{i-1}) = a_n - a_0$

a_n - {a_{n-1}}
{a_{n-1}} - {a_{n-2}}
...
a_1 - a_0

---

$\sum_{i=0}^{n}2^i = 2^{n+1}-1$

General: $\sum_{i=0}^{n}a^i = \frac{a^{n+1}-1}{a-1}$ where $a \neq 1$

---

Important Problem Types

• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems

Important Design/Problem Solving Techniques

• Brute Force/Exhaustive
• Greedy
• Divide and Conquer
• Decrease and Conquer
• Transform and Conquer
• Space and Time Tradeoff
• Dynamic Programming
• Iterative Improvement
• Backtracking
• Branch and Bound

Fundamental Data Structures

• List
  • Array
  • Linked List
  • String
• Stack
• Queue
• Priority Queue/Heap
• Graph
• Tree
• Set
• Dictionary

The Analysis Framework

Issues:

• Correctness

• Time Efficiency and Space Efficiency

  • Time efficiency (also called time complexity) is a measure of how fast an algorithm in question runs.
  • Space efficiency (also called space complexity) is a measure of the amount of extra memory required by the algorithm in addition to the space needed for its input and output.

• Optimality

Approaches

• Theoretical Analysis (with math)

  • Time efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size
    • Basic operation: the operation that contributes most toward the running time of the algorithm

  $T(n) \approx c_{op}C(n)$

  where $T(n)$ is the running time
  $n$ is the input size
  $c_{op}$ is the execution time for the basic operation
  and $C(n)$ is the number of times basic operation is executed.

  • Examples:

  Problem	Input Size	Basic Op
  Searching for key in a list of $n$ items	Number of list's items	Key comparison
  Multiplication of two matrices	matrix dimensions or total number of elements	Multiplication of two numbers
  Checking primality of a given integer $n$	$n$'s size = number of digits (say in binary representation)	Division
  Typical graph problem	Number of nodes and/or edges	Visiting a node or traversing an edge

• Empirical Analysis

  • Select a specific (typical) sample of inputs
  • Use physical unit of time (e.g. milliseconds) or count actual number of basic operation executions
  • Analyze the empirical data

• For some algorithms, efficiency depends on input form

  • Worst case - $C_{worst}(n)$ = maximum over inputs of size $n$
  • Best case - $C_{best}(n)$ = minimum over inputs of size $n$
  • Average case - $C_{ave}(n)$ = "average" over inputs of size $n$
    • Number of times the basic operation will be executed on typical input
    • NOT the average of worst and best case
    • Expected number of basic operations is considered as a random variable under some assumption about the proability distribution of all possible inputs

Sequential Search Example

Search for a given value in an array

SequentialSearch
Input: An array, $A$, of length $n$ and a search key $K$
Output: The index of the first element of $A$ that matches $K$ or $-1$ if there are no matching elements

  i <- 0
  while i < n and A[i] != K do
    i <- i + 1
  if i < n
    return i
  else
    return - 1

• Worst case: $C_{worst}(n) = n$
  Analyze the algorithm to see what kind of inputs yield the largest value of the basic operation's count $C(n) among all possible inputs of size$n$. Clearly in this case$C_{worst}(n) = n$ if counting key comparisons.

• Best case: $C_{best}(n) = 1$

• Average case:
  To analyze the algorithm's average case efficiency we must make some assumptions about possible inputs of size $n$.
  (a) Assume the probability of a successful search is equal to $p$ $(0 \leq p \leq 1)$
  (b) the probability of the first match occurring in the $i$th position of the list is the same for every $i$

  In the case of a successful search, the probability of the first match occurring in the $i$th position is $\frac{p}{n}$ for every $i$, and the number of comparisons is $i$. In the case of unccessful match, the # of comparisons is $n$ with the probability of such a search being $(1-p)$.

  • $C_{ave}(n) = n(1-p) + [1\frac{p}{n} + 2\frac{p}{n} + ... + i\frac{p}{n} + ... + n\frac{p}{n}]$
    $=\sum_{i=1}^{n}i\frac{p}{n} + n(1-p)$
    $=\frac{p}{n}\sum_{i=1}^{n}i + n(1-p)$
    $=\frac{p}{n} \cdot \frac{n(n+1)}{2} + n(1-p)$
    $=\frac{p(n+1)}{2} + n(1-p)$

  • Is average case important? YES! But rarely easy to do. Probabilistic assumptions are hard to verify.

  • For most algorithms, we will simply quote already proven average case analysis

Asymptotic Analysis

'Big Oh'
$\mathcal{O}(g(n))$

The set of all functions with a lower or the same order of growth as $g(n)$

Examples:
$n \in \mathcal{O}(n^2)$
$1000n + 45 \in \mathcal{O}(n^2)$
$\frac{n(n-1)}{2} \in \mathcal{O}(n^2)$

$n^3 \notin \mathcal{O}(n^2)$
$\frac{n^3}{10000} \notin \mathcal{O}(n^2)$
$2^n \notin \mathcal{O}(n^2)$

---

$\Omega(g(n))$

The set of all functions with a higher or same order of growth as $g(n)$

$n^3 \in \Omega(n^2)$
$\frac{n(n-1)}{2} \in \Omega(n^2)$
$2^n \in \Omega(n^2)$

$1000n \notin \Omega(n^2)$
$\frac{12n^2}{n} \notin \Omega(n^2)$
$n + 5 \notin \Omega(n^2)$

$\Theta(g(n))$

The set of all functions with the same order of growth as $g(n)$

$t(n) \in \mathcal{O}(g(n))$ if $t(n)$ is bounded above by some constant multiple of $g(n)$ for all large $n$.

$12n + 44 \in \mathcal{O}(n)$
$12n + 44 \leq 12n + 44n$, $\forall n \geq 1$
$\leq 56n$ where $c = 56n$ and $n_0 = 1$

$t(n) \in \Omega(g(n))$ if $t(n)$ is bounded below by some constant multiple of $g(n)$ for all large $n$.

$t(n) \in \Theta(g(n))$ if $t(n)$ is bounded both above and below by some constant multiple of $g(n) for all large$n$

Example:
$\log (n!) \in \Theta(n \log n)$
$\log (n1) = \log (1) + \log(2) + ... + \log(n)$
$\leq \log(n) + \log(n) + ... + \log(n)$

$\log(n!) \geq \log(\frac{n}{2}) + \log(\frac{n}{2}+ 1) + ... + \log(n)$
$\geq \log(\frac{n}{2}) + \log(\frac{n}{2}) + ... + \log(\frac{n}{2})$
$\geq \frac{n}{2} \log(\frac{n}{2})$

General Plan for Analysis (Nonrecursive algorithms)

• Decide on parameter $n$ indicating input size
• Identify Algorithm's basic operation
• Determine best, worst, and average cases for input size $n$
• Set up a sum for the number of times the basic operation is executed
• Simplify the sum using standard formulas and rules (Appendix A in the textbook)

---

Limits?

Basic Efficiency Classes and Descriptions (p59)

Algorithm Example (if time permits)

Interval Scheduling

* [Summation Review](#summation-review)