CSC152 2006S, Class 34: Algorithm Analysis (2): Formalizing the Notation
Admin:
* There are no readings for tomorrow.
* An eboard for yesterday is available.
* I was disappointed in some of you folks yesterday ...
* that so few seemed to remember the efficient exponentiation algorithm.
* that a few of you seemed to be reading email during class. (Note that it's a bad idea to do so when there's a faculty member right next to you.)
* that so few of you participated
* I was tempted to give you a quiz today.
* Today will continue the lecture/discussion model. Tomorrow will be lab.
Overview:
* A better exponentiation function?
* Notes from yesterday.
* Asymptotic Analysis.
* Asymptotic Analysis in Practice.
* Supporting Asymptotic Analysis with Experiments.
* Eliminating Constants.
* Relating Functions.
Can you do better than the "divide and conquer" strategy for
exponentiation?
Rather than x^n = (x^(n/2))^2, do x^n = (x^(n/b))^b for
some big number b
Let's try some examples
* Whoops , with 3 as b, it takes longer
* The problem is that, althoguh we divide the exponent more times, we also do more multiplications.
* Also, we'll still get log_something, which is not constant
The solution
x^n = e^nlnx
Moral: Sometimes you need to think "outside the box".
---
/Lessons from Monday/
* Many factors make an algorithm "good" or "better". (In this course, we will often focus on efficiency.)
* The problem domain also has a big effect.
* Cute facts
* The compiler precomputes additions (and other arithmetic operations) when possible
* Roller Coaster Tycoon draws 1000's of objects again and again
* When we compare the run-time efficiency of algorithms, we tend
to abstract away details so that you can compare them more
easily.
* Constant multipliers and adders do not matter
* The Big-O thing is how we abstract away details.
* When we analyze algorithms, we can consider
* Worst case
* Average case
* Best case
Analyzing Algorithms: Math, Science, and Engineering Approaches
Math: A formal definition of Big-O that supports "you can ignore multipliers and constant addition"
Engineering: Informally analyze the Big-O running time of an algorithm
Science: Experimental hypothesis verification
Formal definition - What do we want it to indicate?
* A focus on the shape of the run-time-vs-input-size curve, rather than particular details (such as multiplication factors)
* A sense that we don't care too much about how it behaves for small input sizes
O(g(n)) is a set of functions.
How to define sets
* List the elements: DaysOfTheWeek = { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday }
* Give equations that specify elements
0 is in N
if i is in I, then i+1 is in N
* Give a predicate that indicates whether or not a value is in the set
f(n) is in O(g(n)) if and only if
Exist n0 and c such that
for all n > n0, |f(n)| <= |c*g(n)|
Why is this useful?
* It helps us eliminate constant multipliers
Compare f(n) = 0.5*n to g(n) = 100*n
* Does big-O support the claims that f(n) is in O(g(n))
and g(n) is in O(f(n))?
* For any positive n, 0.5*n < 100*n, so let c=1 and n0 be 0
=> f(n) is in O(g(n))
* 100*n <= c*0.5n as long as c>=200 and n>0
=> g(n) is in O(f(n))
* It helps us eliminate smaller-order terms
Compare f(n) = n + 5 to g(n) = 2n
n+5 <= 2n when n>5 so, f(n) is in O(g(n))
2n <= c*(n+5) when c is 2
Similarly 2n is in O(2n+5)
and 2n+5 is in O(2n)
The primary outcome for computer scientist: We can talk about the
running time without worrying about constant multipliers or
smaller order terms, and say O(n), O(n^2), O(logn) and not
something like O(3n+5)
How do we use big-O notation?
* We count the steps in a procedure
* We express the running time as a function of the input size
* We throw away constant multipliers and lower-order terms
Counting steps (worst case analysis):
* Arithmetic, Comparison, Assignment, I/O: 1 step
* Conditional: Maximum of the cost of the branches
* Loop: Count number of repetitions and cost of body, multiply
* Sequence of statements: Add 'em up
* Function call: Compute the cost of the called function
public int smallest(Comparable[] values)
{
Comparable tmp = values[0];
for (int i = 1; i < values.length; i++) {
for (int j = i; j < values.length; j++) {
if (!(values[i] instanceof Integer) {
throw new StupidUserexcpeiont();
}
} // for
if (tmp.compareTo(values[i]) > 0) {
tmp = values[i];
} // if
} // for
return tmp;
} // smallest
About 5*n + 2 steps, O(n)