Problem from DS&A (Version 1):

  sum(x^i,i=0..n) = x^0 + x^1 + ... + x^n (geometric sum)

Proposed approach:

  sum = 1 + x + x*x + x*x*x + ....
  find product of each term as a loop

Code:

  /* 1  */ int sum = 0;
  /* 2a */ for ( int i=0;
  /* 2b */      i <= n; 
  /* 2c */      i++ ) { 
  /* 3  */    int prod = 1;
  /* 4a */    for ( int j = 0; 
  /* 4b */          j < i;
  /* 4c */          j++)
  /* 5  */       prod *= x; 
  /* 6  */    sum += prod; }
  /* 7  */    return sum;

Notes: 

  outer loop happens 0,1,...,n   = n+1 times
  inner loop happens 0,1,...,i-1 = i   times

Analysis:

  S  | Time
  ---+-------------------------------------------------------------------------
  1  | 2                1 assign +1 value (constants "count" as an op)
  2a | 2                initialization (happens before 1st loop)
  2b | 3(n+2)           2 values + 1 comparison done (n+2) times
                        Why n+2 times? outer loop happens n+1 times.
                        After the last loop, there's one more comparison!
  2c | 4(n+1)           2 values+1 add+1 assign, which are done (n+1) times
  3  | 2(n+1)           1 value + 1 assign done (n+1) times (from outer loop)
  4a | 2(n+1)           1 assign + 1 value done (n+1) times (from outer loop)
  4b | 3sum(i+1,i=0..n) 3 ops done i+1 times for each outer loop (n+1)
  4c | 4sum(i,i=0..n)   4 ops done i times for each outer loop (n+1)
  5  | 4sum(i,i=0..n)   4 ops done i times for each outer loop (n+1)
  6  | 4(n+1)           4 ops done for n+1 outer loops
  7  | 2                1 retrieval+1 return

Total time for code: 

  add constants: 2+2+6+4+2+2+4+2 = 24
  
  add sums: 

      use formula sum(i,i=1..n) = (n)(n+1)/2   = (n^2)/2 + n/2
      so, sum(i=0..n,i) = 0 + (n)(n+1)/2       = (n^2)/2 + n/2
       and sum(i=0..n,i+1) = 0 + n + (n)(n+1)/2 = (n^2)/2 + 3n/2
 
      sum of n^2 terms: (3 + 4 + 4)(n^2)/2)    = (11/2)(n^2)
      sum of n terms: (3+4+2+2+9/2+4/2+4/2+4)n = (47/2)(n)
 
  result = (11/2)*n^2 + (47/2)*n + 24
 (note: check the 24, might be off by 1 from sum(i=0..n,i+1)?)