Changes 10/8/14

Java:

• I finally realized why the equation n( n + 1 ) / 2 comes up so much in measuring efficiency of algorithms.  It is the identity of 1 + 2 + . . . + n.  So for algorithms that have multiple loops, this comes in handy, because things tend to increase from 1 to n.
• For example, in the algorithm:

  sum = 0
  for i = 1 to n
  { 
    for j = 1 to i
      sum = sum + 1
  }

• In this image I wrote out what the algorithm would do when n = 5.  I then counted up the number of additions and assignments (which was something they did in the textbook), and saw that the number of assignments matched up with what the book said.  They found that there were 1 + n(n + 1) / 2 assignments in this loop and n(n + 1) / 2 additions, leading to an overall operation cost of n² + n + 1.  This matches up with what I calculated at the bottom of the page.
•