entries/StuartLiv/ThetaFibN.java


1
2
3
4
5
6
7
8
9
10
11
12
13

public class ThetaFibN {

	//Fibonacci(n) is asymptotically in ϴ(Fibonacci(n))
	public int Fibonacci(int n) {
		String reference = "0";
		int fib = 1;
		for(int i = 1; i <= n; i++) {
			fib = reference.length();
			reference = reference.replace("0", "").replace("1", "0") + "1".repeat(fib);
		}
		return fib;
	}
}