| Given two different algorithms that solve the
same problem, Weiss'
wants to know if there is a way to determine if one is faster than the
other. If you implement the programs and measure their actual execution time, this is an emprical analysis. If you study the properties of the algorithm using mathematics and rules of logic, this is a formal analysis. Actually, the question is "algorithm X faster than algorithm Y" is too vague, because it depends on how many data items are being processed. For example, binary search is faster than linear search for large data sets, but for small data sets, linear search is faster. Don't bother to tell me "this algorithm takes longer the larger the data set" because this is true of all algorithms. What we want to know is the rate at which the running time increases. When the text asks for the running time of an algorithm, it is implied that he is asking for the running time as a function of the number of data items. We estimate the running time of an algorithm by counting the number of basic operations it performs, e.g, moving data, comparing data, arithmetic operations. Example: Weiss pg 35. We only need to estimate the running time, we don't need an exact answer, we just need to know with enough accuracy to compare it to a different algorithm. All we need is an "order of magnitude" estimate. Derive the big O order in this manner:
Some algorithms may perform differently with under differing input conditions, so it may be helpful to characterize the best, worst, and average-case running times. If a question asks for running time without specifying which case, it usually means worst-case. |
| Sequence A sequence of computations will take a constant amount of time to execute. It is independent of how many input data items are being processed. Decisions Also constant time. "Fixed" Loops A loop that performs a fixed number of iterations is still considered constant time. E.g., for (int days = 1; days <= 7; days++) The number of iterations doesn't depend on the number of input data items. General Loops When a loop processes a set of input data items, the number of iterations is variable, so we characterize the running time as a function of the number of data items. for (int days = 1; days <= number_of_days; days++) { total = total = days * 30; } would be O(n) or linear time. Nested Loops Multiply the running time of the loop body by the product of the sizes of all the loops. for (int days = 1; days <= days.length; days++) { for(int items = 1; items <= days.length; days++) { days[items] = days[items] / days.length; } } would be O(n2) or quadratic time. |
| Function |
Common Name |
Running Time* |
| n! |
Factorial |
|
| 2n |
Exponential |
> 100 years |
| nd, d>3 |
Polynomial |
|
| n3 |
Cubic |
31.7 years |
| n2 |
Quadratic |
2.8 hours |
| n log n |
1.2 seconds |
|
| n |
Linear |
0.1 seconds |
| √ n |
Root-n |
0.00032 seconds |
| log n |
Logarithmic |
0.000012 seconds |
| 1 |
Constant |
0.000001 |