Asymptotic Notation (and Execution Time)

Return to List of Lectures

Previous Lecture

• Questions?
• Polynomial Evaluation
  • 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

  • Execution time?
    • Count red steps as the key ones
    • Note that power = power * x is done a different number of times on each iteration of the i loop
    • You have to add all these numbers together
      
    • Number of times a key step gets executed = n(n+1) / 2 + (n+1)
      • = an² + bn + c
      • Quadratic
  • Another algorithm: Horner’s Rule
    

    poly2( a0..n, x )
        p = 0
        for i = n down to 0
            p = p * x + ai
        end
        return p

    • Look at how value of p evolves:
      • p = 0 + a_n x² + a_n-1 x + a_n-2 + …
    • Key step done n+1 times
      • Linear time — so this algorithm is quantifiably better than the first one
• Asymptotic Notation
  • Section 3.1
    • Different asymptotic classes
      • Θ( f(n) ): between c₁ f(n) and c₂ f(n)
      • O( f(n) ): ≤ c f(n)
      • o( f(n) ): < c f(n)
      • Ω( f(n) ): ≥ c f(n)
    • Properties
      • Transitivity
      • Reflexivity
        • Sometimes: f(n) in O( f(n) ) but f(n) not in o( f(n) )
    • Theorem: f(n) in Θ( g(n) ) iff f(n) in O( g(n) ) and f(n) in Ω( g(n) )
      • Proof
        
  • Show that n + sin(n) is in O(n² )
    • Need n + sin(n) ≥ 0, so n₀ ≥ 1
    • Need n + sin(n) ≤ c n²
    • Pick c = 1, then for n₀ = 2, n + sin(n) ≤ n² whenever n ≥ n₀ = 2
• Next
  • Proving correctness
  • Read section 2.1 up to “Pseudocode conventions”

Next Lecture