What is the time and Space complexity (Big-O notation) for printing Fibonacci series using recursion and loop? There is an loop used to print the Fibonacci numbers does that also included while calculating time and space complexity?
Is my analysis below correct?
Using Recursion
public int printFibonacciSeries(int n) {
if (n <= 1) {
return n;
}
return printFibonacciSeries(n - 1) + printFibonacciSeries(n - 2);
}
public static void main(String[] args) {
...
FibonacciSeries fibonacciSeries = new FibonacciSeries();
for (int i = 0; i < n; i++) {
System.out.println("i=" + i + " and " + fibonacciSeries.printFibonacciSeries(i));
}
}
My analysis:
- Time Complexity: O(n 2n) - since for all n values the Fibonacci is calculated (calculating nth Fibonacci is 2n)
- Space Complexity: O(1) - recursive call are added to stack but then once the execution is completed the value are delete from stack
Using Loop
public void printFibonacciSeriesWithLoop(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
if (i <= 1) {
arr[i] = i;
} else {
arr[i] = arr[i-1] + arr[i-2];
}
}
Arrays.stream(arr).forEach(System.out::println);
}
public static void main(String[] args) {
...
FibonacciSeries fibonacciSeries = new FibonacciSeries();
fibonacciSeries.printFibonacciSeriesWithLoop(i);
}
My analysis:
- Time Complexity: O(n + n) or O(2n) ⟹ O(n) - the first O(n) is for calculating and another O(n) for printing, so 2n, but drop the constant
- Space Complexity: O(n) - n values are stored in the array