• The Process:
  • Write the necessary code
  • Measure the running time and space requirements
• An Important Caveat:
  • It would be a big mistake to run the application only once
  • Instead, one must develop a sampling plan (i.e., a way of developing/selecting sample inputs) and test the application on a large number of inputs

• It is often very difficult to test algorithms on a large number of representative inputs.
• The efficiency can't be known a priori and it if often prohibitively expensive to implement and test an algorithm only to learn that it is not efficient.

• The Idea:
  • Obtain an upper and/or lower bound on the time and space requirements
• An Observation:
  • Bounds are used in a variety of contexts

• A Common Question at Job Interviews:
  • How many hairs do you have on your head?
• Obtaining a Bound:
  • Suppose a human hair occupies at least a square of 100 microns on a side (where one micron is one millionth of a meter)
  • Then, each hair occupies at least 0.00000001 m² in area
  • Suppose further that your head has at most 400 cm² in total area (or 0.04 m²)
  • Then, your head has at most 4 million hairs

• Worst Case Analysis:
  • Instead of trying to determine the "actual" performance experimentally, one instead attempts to find theoretical upper bounds on performance
• Some Notation:
  • The worst case running time for an input of size $n$ is denoted by $T(n)$
  • The worst case space requirement for an input of size $n$ is denoted by $S(n)$

• Which is Better?
  • An algorithm with worst case time of $n^{2}+5$
  • An algorithm with worst case time of $n^{2}+2$
• Do You Care When $n=1000$?
  1,000,005
  1,000,002

• The Idea:
  • When comparing algorithms based on their worst case time or space it seems best to consider their asymptotic performance (i.e., their performance on "large" problems)
• Applying this Idea:
  • Consider the limit of the worst case time or space

• Compare Two Alogorithms When:
  • One requires $n^{3}$ iterations and one requires $2^{n}$ iterations
  • Each iteration requires one microsecond (i.e., one millionth of a second)
• Different Problem Sizes:

  • $T(n)$	$n=10$	$n=25$	$n=50$	$n=75$
    $n^{3}$	0.001 sec	0.016 sec	0.125 sec	0.422 sec
    $2^{n}$	0.001 sec	33.554 sec	35.702 yrs	11,979,620.707 centuries

• Defining "little o":
  • $T=o[f(n)] \mbox{ iff } \lim_{n \rightarrow \infty } \frac{T(n)}{f(n)} = 0$
• An Example: $n^{2}+5$
  • "little o" of $n^{3}$ since $\lim_{n \rightarrow \infty }[\frac{(n^{2}+5)}{n^{3}}]=0$

• Interpreting "little o":
  • When $T$ is "little o" of $f$ it means that $T$ is of lower order of magnitude than $f$
• Defining "big O":
  • $T=O[f(n)]$ iff there exist positive $k$ and $n_{0}$ such that $T(n) \leq k f(n)$ for all $n \geq n_{0}$
• Interpreting "big O":
  • $T$ is not of higher order of magnitude than $f$

• Show:
  • $n^{2}+5$ is $O(n^{2})$
• Choose $k=3$ and $n_{0}=2$ and observe:
  • $n^{2}+5 \leq 3n^{2}$ for all $n \geq 2$

• Defining "Big Omega":
  • $T= \Omega [g(n)]$ iff there exists a positive constant $c$ such that $T(n) \geq c g(n)$ for an infinite number of values of $n$
• An Example: $n^{2}+5$
  • Is $\Omega (n^{2})$ since, setting $c=1$:
    $n^{2}+5 \geq n^{2}$ for all $n \geq 0$

1. If $T_{1} = O[f_{1}(m)]$ then $k T_{1} = O[f_{1}(m)]$ for any constant $k$
2. If $T_{1}= O[f_{1}(m)]$ and $T_{2}= O[f_{2}(m)]$ then $T_{1}T_{2}=O[f_{1}(m)]O[f_{2}(m)]$
3. If $T_{1}= O[f_{1}(m)]$ and $T_{2}= O[f_{2}(m)]$ then $T_{1}+T_{2}= \max{O[f_{1}(m)], O[f_{2}(m)]}$

Suppose an algorithm has three "steps" with running times of $O(n^{4})$, $O(n^{2})$, and $O(\log n)$.

Then, it follows from rule 3 that the running time for the entire algorithm is $O(n^{4})$.

Suppose an algorithm has one "step" with a running time of $O(n)$ and that it repeats this "step" (in a loop) 1000 times.

Then, it follows from rule 1 that the running time for the entire algorithm is $O(n)$.

What is the asymptotic bound on the worst case time efficiency of the following recursive algorithm?

    int factorial(int n)
    {
      // Check for valid input
      if (n > 12) return -1;


      if ((n == 0) || (n == 1)) return 1;

      return n*factorial(n-1);
    }
    

What is the asymptotic bound on the worst case time efficiency of the following iterative algorithm?

    int factorial(int n)
    {
      int i, value;
    
      // Check for valid input
      if (n > 12) return -1;
    
      value = 1;
      for (i=2; i<=n; i++) {
    
        value *= i;
      }
    
      return value;
    }
    

What is the asymptotic bound on the worst case time efficiency of the following algorithm? What about the space efficiency?

    int factorial(int n)
    {
    int f[13]={1,1,2,6,24,120,720,5040,40320,
               362880,3628800,39916800,479001600};

      // Check for valid input
      if (n > 12) return -1;

      return f[n];
    }