Efficiently compute fibonacci number in Java

1. Inefficient approach for computing fibonacci number by using recursion. This takes big O of 2 to the n square time. O(2^N)

public static int fibonacciRecursive(int n) {
	if (n==0) return 0;
	if (n==1) return 1;
	
	return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
}

2. Efficient way for computing fibonacci number by using recursion with memorization. This takes big O of N time. O(N)

public static int fibonacciRecursiveMem(int n) {
	return fibonacciRecursiveMem(n, new int[n+1]);
}

public static int fibonacciRecursiveMem(int i, int mem[]) {
	if (i==0 || i==1) return i;
	
	if (mem[i] == 0) {
		mem[i] = fibonacciRecursiveMem(i-1, mem) + fibonacciRecursiveMem(i-2, mem);
	}
	
	return mem[i];
}	

3. Another efficient way for computing the fibonacci number using iterative approach. This also takes big O of N times. O(N)

public static int fibonacciIterative(int n) {
    int a = 0, b = 1, c;
    if (n == 0) return a;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

All together with a test

public class Fibonacci {
	
	//O(2^N)
	public static int fibonacciRecursive(int n) {
		if (n==0) return 0;
		if (n==1) return 1;
		
		return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
	}
	
	
	
	//O(N)
	public static int fibonacciRecursiveMem(int n) {
		return fibonacciRecursiveMem(n, new int[n+1]);
	}
	
	public static int fibonacciRecursiveMem(int i, int mem[]) {
		if (i==0 || i==1) return i;
		
		if (mem[i] == 0) {
			mem[i] = fibonacciRecursiveMem(i-1, mem) + fibonacciRecursiveMem(i-2, mem);
		}
		
		return mem[i];
	}	
	
	
	//O(N)
	public static int fibonacciIterative(int n) {
        int a = 0, b = 1, c;
        if (n == 0) return a;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
 
	
	
	public static void main(String args[]) {
		int n = 40;
		long current;
		long timeTaken;
		
		current = System.currentTimeMillis();
		int fib1 = fibonacciRecursive(n);
		timeTaken = System.currentTimeMillis() - current;
		System.out.println("The "+ n +"th fibonacci number is " + fib1 + " Time taken to compute it recursively: " + timeTaken + " milliseconds");
		
		current = System.currentTimeMillis();
		int fib2 = fibonacciRecursiveMem(n);
		timeTaken = System.currentTimeMillis() - current;
		System.out.println("The "+ n +"th fibonacci number is " + fib2 + " Time taken to compute it recursively with memorization: " + timeTaken + " milliseconds");

		
		current = System.currentTimeMillis();
		int fib3 = fibonacciIterative(n);
		timeTaken = System.currentTimeMillis() - current;
		System.out.println("The "+ n +"th fibonacci number is " + fib3 + " Time taken to compute it iteratively: " + timeTaken + " milliseconds");
		
	}
}

Output:

The 40th fibonacci number is 102334155 Time taken to compute it recursively: 552 milliseconds
The 40th fibonacci number is 102334155 Time taken to compute it recursively with memorization: 0 milliseconds
The 40th fibonacci number is 102334155 Time taken to compute it iteratively: 0 milliseconds