• 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?

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

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