package Common;

/**
 *
 * @author dimitar
 */
public class Common {
    // Recursive Fibonacci computation
    // Running time - O(2^n)
    // Space - O(n)
    public int fibR(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        return fibR(n - 1) + fibR(n - 2);
    }
    
    // Iterative Fibonacci computation
    // Running time - O(n)
    // Space - O(1)
    public int fibI(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }
        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        
        int[] a = new int[n + 1];
        a[1] = 1;
        a[2] = 2;
        for(int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }        
        return a[n];
    }
    
    // Cached (Memorization) Fibonacci computation
    // Running time = O(n)
    // Space - O(n)
    // Note - cache size should be configurable
    private int[] cache = new int[100000];
    public int fibM(int n) {
        if(n < 0) {
            throw new IllegalArgumentException("Must be a non-negative number");
        }
        
        if(n == 0) { return 0; }
        if(n == 1) { return 1; }
        
        if(cache[n] != 0) {
            // return cached result
            return cache[n];
        }
        // cache the result
        cache[n] = fibM(n - 1) + fibM(n - 2);
        return cache[n];
    }
}

@@ -921,24 +921,496 @@
 %0A    %7D%0A    %0A
+    // Iterative Fibonacci computation v2%0A    // Runnint time - O(n)%0A    // Space - O(1)%0A    public int fibI2(int n) %7B%0A        if(n %3C 0) %7B%0A            throw new IllegalArgumentException(%22Must be a non-negative number%22);%0A        %7D%0A        %0A        if(n == 0) %7B return 0; %7D%0A        if(n == 1) %7B return 1; %7D%0A        %0A%09%09int p1 = 1;%0A%09%09int p2 = 2;%0A%09%09int result = 0;%0A%09%09for(int i = 2; i %3C n; i++) %7B%0A%09%09%09result = p1 + p2;%0A%09%09%09p1 = p2;%0A%09%09%09p2 = result;%0A%09%09%7D%0A%09%09return result;%0A    %7D%0A    %0A
     // Cache

Update Common.java