T(n) = T(n/2) + T(n/4) + T(n/8) + (n)

n---------------------------------> n

                             (n/2)         (n/4)           (n/8)--------------> (7/8)n

                         n/4 n/8 n/16  n/8 n/16 n/32  n/16 n/32 n/64)--------> (49/64)n
                                            ...

T(n) = T(n/2) + T(n/4) + T(n/8) + n
    <= c/2*n + c/4*n + c/8*n + n
     = (7/8*c + 1) * n
    <= cn (when c >= 8)

long fib(long n){
 if(n <= 1) return n;
 else return fib(n-1) + fib(n-2);
}

static ArrayList<Long>fib_global = new ArrayList(1000);
  //delcare a global variable that can be appended to
long fib(long n){
   if(n >= fib_global.length)fib_global.add(fib(n-1) + fib(n-2));
   return fib_global.get(n);
}