CSC152 2005F, Class 35: Algorithm Analysis (3)
Overview:
* Sorry about problem in lab.
* Eryn wants to know why you don't visit her.
* Homework to be determined.
Admin:
* Review
* Detour: Counting deletions
* Lab discussion
* Recurrence relations
Review:
* Focusing on analyzing the running time of algorithms
* Big O analysis
* Puzzling mathematical notation
* The notation lets us ignore things (say that the "don't matter")
* Constant multipliers:
n^2 vs. n matters more than 2n vs 3n
n^2 will dominate d*n no matter what d we choose
* Lower order terms:
n^2 plus something smaller than n^2 is not much different
than n^2 for big enough n
* If two methods are both O(n^2), big O analysis does not provide a good technique for deciding which is faster.
* Experiments will help
* Big O notation: See real whiteboard (no photos available)
* Use this to prove the things we expect/want
* Return to the notation in CSC301
Detour: Counting deletions
int len = stuff.size(); // O(1)
for (int i = 0; i < len; i++) { // O(len) or O(n) repetitions
stuff.remove(0); // O(n)
}
O(n) repetitions of an O(n) step is O(n^2)
Does it make a difference that we've said remove is O(n) when,
for many values, it's constant.
* We're bounding above, not bounding exactly, so it's okay.
* In real life (or at least computer life) is strive for a "close" upper bound
* Let's do the more careful analysis, only in terms of deletion
N + (N-1) + (N-2) + (N-3) + .... + 5 + 4 + 2 + 1
That sum has the value N(N+1)/2 is O(N^2)
Lab
For exptFor(x,n), what is the running time in terms of n?
+ O(n^2)
+ O(n) ****
BigDecimal result = new BigDecimal(1.0);
for (int i = 0; i < n ; i++) { // N repetitions
this.step();
result = result.multiply(x); // c steps
}
return result;
For exptWhile(x,n), what is the running time in terms of n?
public BigDecimal exptWhile(BigDecimal x, int n)
{
BigDecimal accumulator = new BigDecimal(1);
// need to repeatedly reduce the power. Idea:
// currentx^currentn * accumulator = originalx^originaln
while (n > 0) {
this.step();
// If n is even, divide it by two and multiply x by
// itself, using the amazing rule that
// (x^n = (x^2)^(n/2))
if ((n % 2) == 0) {
// Recursive version: expt3(x.multiply(x), n/2, accumulator);
n = n/2;
x = x.multiply(x);
} // n is even
// If n is odd, subtract 1 from it and ..
else {
// Recursive version: expt3(x, n-1, x.multiply(accumulator));
n = n - 1;
accumulator = x.multiply(accumulator);
} // n is odd
} // while
return accumulator;
} // exptWhile(BigDecimal, int)
+ O(n)
+ O(1)
+ O(log_2(n))
Looking at the data, we see that every time the input size (n)
doubles, the running time goes up by a constant (2, in this case).
Hence, the function is O(log_2(n))
Sequential search: Look at each element
Homework: Try again writing the tests for sequential and binary search.
* MAKE A NEW COPY OF Computer.java