lecture 2

• Iterative algorithms

  Expressing algorithms using loops
• Tools to reason about iterative algorithms

  • Loop invariants
  • Loop control variables
  • Order-of-growth ("big O") notation
• Total correctness

  For all inputs, the algorithm produces the desired result
• Partial correctness

  If the algorithm terminates, it produces the desired result
• Total correctness = partial correctness + termination
• Worst-case time analysis ⇒ termination
• Loop invariant


  A property that holds before and after each execution of the loop
• Steps in using loop invariants


  1. Establish invariant before loop

  2. Maintain invariant in loop body

  3. Use invariant after loop
• Loop control variable


  A variable that is initialized before the loop, used in the loop condition, and modified in the loop body
• Good practice for loop control variables:
• Input size


  The aspect of the input that determines the algorithm's complexity
• Fundamental step

  The basic operation the algorithm performs, whose number of executions determines the algorithm's complexity
• Worst case

  The input that gives the maximum number of steps for the algorithm
• Order-of-growth notation (Big-O)


  A simplified view of a cost function, restricting attention to the term that grows fastest for large inputs and ignoring constant factors