Big-Oh Analysis of Algorithms
Analysis of algorithms does not just mean running them on the computer to see which one is faster. Rather it is being able to look at the algorithm and determine how it would perform. This is done by looking at the order of magnitude of the algorithm. As the number of items(N) changes what effect does it have on the number of operations needed to execute(time). This method of classification is referred to as BIG-O notation.
How can we analyze the algorithm without using a computer? Imagine that each time the program is run, the statements turned a darker shade of grey. The darkest statement would be the one that is executed the most times. Analyzing this statement would allow us to determine the running time of the algorithm.
void swap(double &a, double &b)
double temp = a;
a = b;
b = temp;
void selSort(apvector &L)
int i, j, min, N = L.length();
for (i=0; i<N-1; i++)
min = i;
for (j = i+1; j<N ; j++)
if (L[j] < L[min])
min = j;
swap (L[i], L[min]);
The worst statement (executes most times) is if (L[j] < L[min]). First time through outer loop it executes N-1 times, then N-2, then N-3 down to 1. So the number of times the statement executes is the sum of the numbers 1 to N-1.
which is equal to
This would be considered order O(N2) , since only the most significant term is considered. This is a quadratic time sorting algorithm.
To analyze a function analyze each statement in the function. The statement that has the greatest complexity determines the order of the function. Some helpful rules:
- Simple statements such as assignment statements are O(1), since their execution time is not dependent on the amount of data. The exception would be assigning one array variable to another which would be O(n), where n represents the size of the array.
- The running time for a function call is just the running time for the function's body, plus the time to set up the parameters. Setting up the parameters is O(1), unless a large structure is passed as a value parameter, in which case that structure must be copied into the parameter which is O(n).
- "In an if/else statement, the test (which is usually O(1)) and one of the conditional statements are executed. Since you generally cannot determine the result of the test ahead of time, you should assume the worst case, and thus the running time of the if/else will be the sum of the running time of the test and the running time of the worst-case statement."
- Addition Rule "You can combine sequences of statements by using the addition rule, which states that the running time of a sequence of statements is just the maximum of the running times of each individual statement."
- Multiplication Rule This is used to determine the running time for a loop. "You need to determine the running time for the loop's body and the number of times the loop iterates. Frequently you can just multiply the running time of the body by the number of iterations."
Continue to: Unit 1