The Efficiency of Algorithms
An Introduction |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
\(T(n)\) | \(n=10\) | \(n=25\) | \(n=50\) | \(n=75\) |
\(n^{3}\) | 0.001 sec | 0.016 sec | 0.125 sec | 0.422 sec |
\(2^{n}\) | 0.001 sec |
33.554 sec
|
35.702 yrs
|
11,979,620.707 centuries
|
Asymptotic Bound | Name |
\(O(1)\) | Constant |
\(O(\log n)\) | Logarithmic |
\(O(n)\) | Linear |
\(O(n^{2})\) | Quadratic |
\(O(n^{3})\) | Cubic |
\(O(a^{n})\) | Exponential |
\(O(n!)\) | Factorial |
Suppose an algorithm has three "steps" with running times of \(O(n^{4})\), \(O(n^{2})\), and \(O(\log n)\).
Then, it follows from rule 3 that the running time for the entire algorithm is \(O(n^{4})\).
Suppose an algorithm has one "step" with a running time of \(O(n)\) and that it repeats this "step" (in a loop) 1000 times.
Then, it follows from rule 1 that the running time for the entire algorithm is \(O(n)\).
What is the asymptotic bound on the worst case time efficiency of the following recursive algorithm?
int factorial(int n) { // Check for valid input if (n > 12) return -1; if ((n == 0) || (n == 1)) return 1; return n*factorial(n-1); }
What is the asymptotic bound on the worst case time efficiency of the following iterative algorithm?
int factorial(int n) { int i, value; // Check for valid input if (n > 12) return -1; value = 1; for (i=2; i<=n; i++) { value *= i; } return value; }
What is the asymptotic bound on the worst case time efficiency of the following algorithm? What about the space efficiency?
int factorial(int n) { int f[13]={1,1,2,6,24,120,720,5040,40320, 362880,3628800,39916800,479001600}; // Check for valid input if (n > 12) return -1; return f[n]; }