1. Big Oh for non-recursive functions.

   1. Find a big-O estimate for the running time (in terms of n) of the following function (with explanation)

      int mysterySum( int n ) { int i, j, s=0; for(i=0; i < n; i++) { for(j=0; j < i; j++) { s += i; } } }

   2. Is this version of mysterySum faster? Is the big-O analysis different?

      int mysterySum1( int n ) { int i, j, s=0; for(i=0; i < n; i++) { int i2 = i*i; for(j=0; j < i; j++) { s += i2; } } }

   3. Replace the inner loop in mysterySum by an O(1) expression and compute the running time of the new program.

   4. Find a single O(1) expression giving the same result (A mathematical expression, not code). Hint: Evaluate the function by hand (or compile and run the code) for a few values of n and try to see the pattern.

      Notice: You have to find a mathematical formula, not a piece of code. Start with the expression you derived in part c above (hint: It is a series) and find the sum of the series any way you want (including looking it up).