* 12.1(a,c,e,g,j,l,o), 12.2(a,c,e,g,j,l,o), 12.5(a,c,e,g), 12.6(a,d,h).
* Doing exercises is a good way to check if you really understand this stuff or not.
Reading Assignments
* Ch 12.7 - end of Ch 12. (Fri)
Assignment #4
* a tough one.
* if stuck, get help!
* due Fri July 21.
Quality of a program:
1. Correctness
2. User interface
3. Ease of maintenance (readabilility, extensibility, etc)
4. Robustness
5. Performance
Performance
* Space efficiency - a measure of the amount of memory or storage a program requires.
* Time efficiency - a measure of how long a program takes to execute.
Performance Analysis
* We will focus on time complexity only.
* We will use Big-O notation.
Function Dominance
* An example of a "cost function",
f(1) = 106 time units
f(10) = 250 time units
f(100) = 10600 time units
f(1000) = 10005100 time units
* Cost functions are difficult to derive.
* Computer scientists use functions that approximate the actual cost.
c g(x) is an upper bound for f(x) for x > some value.
* We use the "order of a function" to express time estimates.
1. "f is of order g"
2. "f = O(g)" - Big O-notation
Big-O notation
* f(n) = 4n2 + 5n + 100
* f is O(n2)
* f(n) = 2n3 + 3n2 + 6n + 1000000
* f is O(n3)
* f(n) = 7n - 7000
* f is O(n)
* f(n) = 100
* f is O(1)
* In general, pick the biggest term, drop constants.
Big-O Arithmetic
1. O(k * f) = O(f)
2. O(f * g) = O(f) * O(g)
3. O(f) > O(g) iff f dominates g
4. O(f + g) = Max(O(f), O(g))
Examples of function dominance
1. xn dominates xm if n > m
2. x dominates log(x)
3. log(x) dominates 1
Exercies
1. O(2 * N) =
2. O(1000000 * N2) =
3. O(2 * N2 + 6 * N + 8 log(N) + 800) =
4. O(4*N) * O(3*N) =
Categories of running time
* O(1) - constant time.
* O(N) - linear time.
* O(N2) - quadratic time.
* O(N3) - cubic time.
* O(log(N)) - logarithmic time.
* O(aN) - exponential time.
Control structures and run-time performance
1. simple statement or expression - O(1).
2. sequence - O(s1 + s2)
s1;
s2;
3. if block - O(cond + s1 + s2)
if (cond) {
s1;
} else {
s2;
}
4. for loop - O(N * s1)
for (i = 0; i < N; i++) {
s1;
}
Examples of C++ functions
const char* Item::get_name(const char* in_name) const
{
return name;
}
* O(1)
int factorial(int n)
{
int x = 1;
for (int i = 1; i < n; i++) {
x = x * i;
} return x;
}
* O(n)
int mystery1()
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
temp = a[i][j];
a[i][j] = a[j][i]; a[j][i] = temp;
}
}
}
* O(N2)
Linear Search
// assume we have an array of sorted integers, a.
Boolean
Item_List::is_member(int x)
{
for (int i = 0; i < size; i++) {
if (a[i] == x) {
return TRUE;
} else if (a[i] > x) {
return FALSE;
}
}
return FALSE;
}
* O(size)
Binary Search
Boolean
Item_List::is_member(int x)
{
int lower = 0;
int upper = size - 1;
int loc = upper / 2;
while (lower <= upper && a[loc] != x) {
if (x > a[loc]) {
lower = loc + 1;
} else {
upper = loc - 1;
} loc = (upper + lower) / 2;
} return (lower <= upper);}
Exercises
* ...is_member(24) - how many iterations?
* ...is_member(100) - how many iterations?
when size == 1, max # iterations == 1
when size == 3, max # iterations == 2
when size == 7, max # iterations == 3
when size == 15, max # iterations == 4
when size == 31, max # iterations == 5
...
when size == 255, max # iterations == 8
...
* O(log2N) or O(log N) - we usually drop the base if it is equal to 2.
* We perform "worst case analysis"