Kenny Wong
CS4800
Extra credit

A situation where work is duplicated can be found in computing Fibonacci numbers. Using a basic implementation to computing the nth Fibonacci:

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

To calculate the 4th Fibonacci, the function would go through:
fibonacci(4) -> 
fibonacci(3) + fibonacci(2) -> 
fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0)
... and so on.

Here we see that fibonacci(3) will end up calling on fibonacci(2). In this way, work will be duplicated, and its running time will be approximately T(1.618^(n+1)) (exponential time, apparently calculating the fibonacci sequence is linked to the golden ratio).


To make this algorithm more efficient, one can use memoization to store precalculated data and then look it up to save calculation time. While using more storage space, it runs more efficiently as it takes very little time to check if it has been calculated before, and if it has been previously calculated, it will save a great deal of time.

Code:

// Outside of method:
Map<Integer,Integer> fibmap = new HashMap<Integer, Integer>();
fibmap.put(0, 0);
fibmap.put(1, 1);

public static int fibonacci2(int n) {
	if (!fibmap.containsKey(new Integer(n))) {
		fibmap.put(n, fibonacci2(n - 1) + fibonacci2(n - 2));
	} 
	return fibmap.get(n);
}

Since finding the nth Fibonacci using this function would only cause calculations of every integer down to 1 just once, with any additional function calls with the same int value being found in the map, the running time here is O(n).