CIS 3020 Part 7
Contents
Complexity
- When computing O(), we are concerned with big values of n
- With big values, constants become ignorable
- Consider the two exponential functions we developed
- Let's count all operations (arithmetic, assignment, references, comparisons, etc.) the same with calls counting 20.
Exponentiation, O(N)
public int expt(int b, int n) {
int result;
if (n<=0) {
result = 1;
} else {
result = b * expt(b, n-1);
}
return result;
}
|
2 1 3 3 28 2 ------ 39 |
Exponentiation, O(log N)
public int expt(int b, int n) {
return fastExpt(b,n);
}
private int fastExpt(int b, int n) {
int result;
if (n<=0) result = 1;
else if (even(n)) result = square(fastExpt(b, n/2));
else result = b * fastExpt(b, n-1);
return result;
}
private int square(int x) {
return (x * x);
}
private boolean even(int x) {
return (x % 2 == 0);
}
|
2 23 2 1 6 67 28 2 1 4 1 6 ------ 143 |
Comparison
- some might argue that the second method is ~3.7 times as expensive
- And, even if it is O(log N), it will be slower than the first method
- Let's look at values to see if this is true...
| N | O(N) | O(log N) | 39*O(N) | 143*O(log N) |
|---|---|---|---|---|
| 2 | 2 | 1 | 78 | 143 |
| 4 | 4 | 2 | 156 | 286 |
| 8 | 8 | 3 | 312 | 429 |
| 16 | 16 | 4 | 624 | 572 |
| 32 | 32 | 5 | 1248 | 715 |
| 64 | 64 | 6 | 2496 | 858 |
| 128 | 128 | 7 | 4992 | 1001 |
| 256 | 256 | 8 | 9984 | 1144 |
| 512 | 512 | 9 | 19968 | 1287 |
| 1024 | 1024 | 10 | 39936 | 1430 |
