JMU
The Efficiency of Algorithms
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


An Obvious Way to Measure Efficiency
Problems with This Approach
An Alternative Approach: Bounds
Bounds (cont.)
Bounds (cont.)
Comparing Different Algorithms
Asymptotic Dominance
I Hate Math - Does Efficiency Really Matter?
Landau Numbers
"big O" Notation
"big O" Notation (cont.)
Lower Bounds on Growth Rates
Categorizing Performance

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

Determining Asymptotic Bounds
  1. If \(T_{1} = O[f_{1}(m)]\) then \(k T_{1} = O[f_{1}(m)]\) for any constant \(k\)
  2. If \(T_{1}= O[f_{1}(m)]\) and \(T_{2}= O[f_{2}(m)]\) then \(T_{1}T_{2}=O[f_{1}(m)]O[f_{2}(m)]\)
  3. If \(T_{1}= O[f_{1}(m)]\) and \(T_{2}= O[f_{2}(m)]\) then \(T_{1}+T_{2}= \max{O[f_{1}(m)], O[f_{2}(m)]}\)
Determining Asymptotic Bounds (cont.)

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})\).

Determining Asymptotic Bounds (cont.)

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)\).

An Example: Factorials

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);
    }
    
An Example: Factorials (cont.)

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;
    }
    
An Example: Factorials (cont.)

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];
    }