In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:
The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling; this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13 and 21.
By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.
Solve using Recursion :
public class FibonacciSeries {
public static void main(String[] args) {
int n = 30;
long startTime = System.nanoTime();
System.out.println(FibonacciSeries(n));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FibonacciSeries(int n) {
if(n==0) return 0;
if(n==1) return 1;
return FibonacciSeries(n-1)+FibonacciSeries(n-2);
}
}
output :
832040
Total Time (nanoseconds) : 6212717
The time complexity for the above solution is exponential, i.e 2^n.
Can we do it in a better time?
Yes, by using dynamic programming and memoizing the previous computed results.
Dynamic Programming Top-Down Approach :
public class FibonacciSeries {
static int[] arr = new int[100];
public static void main(String[] args) {
int n = 30;
long startTime = System.nanoTime();
System.out.println(FibonacciSeries(n));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FibonacciSeries(int n) {
if(n==0) return 0;
if(n==1) return 1;
if(arr[n] == 0)
arr[n] = FibonacciSeries(n-1)+FibonacciSeries(n-2);
return arr[n];
}
}
output:
832040
Total Time (nanoseconds) : 249580
Dynamic programming Bottom-Up Approach :
public class FibonacciSeries {
public static void main(String[] args) {
int n = 30;
long startTime = System.nanoTime();
System.out.println(FibonacciSeries(n));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FibonacciSeries(int n) {
int arr[]=new int[100];
arr[0]=0;
arr[1]=1;
for(int i=2;i<=n;i++)
arr[i]=arr[i-1]+arr[i-2];
return arr[n];
}
}
output:
832040
Total Time (nanoseconds) : 246560
The time complexity for Top-Down and Bottom-Up approach is O(n) and Space complexity is also O(n).
Can we do much better than this?
Yes, we can just store previously two computed results instead of storing all results in an array.
public class FibonacciSeries {
public static void main(String[] args) {
int n = 30;
long startTime = System.nanoTime();
System.out.println(FibonacciSeries(n));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FibonacciSeries(int n) {
int a =0;
int b =1;
if(n == 0)
return a;
if(n == 1)
return b;
for(int i=2;i<=n;i++)
{
int temp = a;
a=b;
b=temp+a;
}
return b;
}
}
output:
832040
Total Time (nanoseconds) : 326229
The Time complexity of the above solution is O(n) and the space complexity is O(1)
