Analyzing Execution Time

Return to List of Lectures

Previous Lecture

• Misc
  • Intro to LaTeX
    • LaTeX = widely used mathematical type-setting program, good to know for serious math writing
    • Tuesday, Sept. 8, 6:00 - 7:30 PM, Welles 26
    • Bring laptop
    • Prof. Leary
  • Class Google group
    • math303-01-fal15-googlegroup@geneseo.edu
    • Use for sending email to class
    • Also shares this document
  • Sign up for grading assignment 1
• Questions?
• Time Analysis
  • Section 2.2
    • RAM model
      • 1 step at a time
      • “Steps” are those that modern computers do in constant time
        • Basic 4 arithmetic operations
        • Control flow, i.e., loops, if (at low level, jumps, branches, may be conditional on comparisons)
        • Data movement
      • Exponentiation is generally not a constant-time operation except for 2^k
    • Times
      • Worst case - most useful, upper bound
      • Average case - expected value of running time over all possible runs (i.e., inputs)
        • About same as worst case in many real cases
      • Best case - special condition makes algorithm work very fast
    • Execution time calculable by adding times for all operations performed by algorithm
      • But order-of-magnitude of result is most important
  • Examples
    • Primality
      

      isprime( n )                Times (Worst Case)
          r = floor( √n )           1
          for i = 2 to r            r
              if n mod i = 0        r-1 = √n - 1
                  return false      0
              end of for
          return true               1

      • What measures input size?
        • Value of n
      • Best-case time?
        • n is even
        • T(n) = c₁ + c₂ + c₃ + c₄ = constant
      • Worst-case time?
        • Count how many times key step (constant time) is done
          • if n mod i = 0
        • √n - 1
    • Evaluating polynomials (without an exponentiation operator)
      • p(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀
      • Input: list of coefficients and value for x
      • Output: p(x)
        

        poly( a0..n, x )
            p = 0
            for i = 0 to n
                power = 1
                for j = 1 to i
                    power = power * x
                end for j
                p = p + ai * power
            end for i
            return p

• Next
  • Analyze running time for poly
  • Find a better algorithm and show that it’s better based on execution time expression
  • Asymptotic notation
    • Read section 3.1

Next Lecture