Problem from DS&A (Version 2):
sum(x^i,i=0..n) = x^0 + x^1 + ... + x^n (geometric sum)

Proposed approach:
  sum = 1 + x + x*x + x*x*x + ....
      = (1 + (1 + (x)(1 + (x)(1 + ... ))))

Code:
/* 1  */ int sum = 0;
/* 2a */ for ( int i=0;
/* 2b */      i <= n; 
/* 2c */      i++ )
/* 3  */    sum = sum * x + 1 ;
/* 4  */ return sum;

Notes: 
  outer loop happens 0,1,...,n   = n+1 times

S  | Time
---+---------------------------------------------------------------------------
1  | 2                1 assign+1 value
2a | 2                initialization (happens before 1st loop)
2b | 3(n+2)           2 values + 1 comparison done (n+2) times
2c | 4(n+1)           2 values+1 add+1 assign, which are done (n+1) times
3  | 6(n+1)           3 value+1 assign+2 ops done (n+1) times
4  | 2                1 retrieval+1 return

Total time for code: 13n+22