Time and space complexity for printing Fibonacci series using recursion and loop

Viewed 1081

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
1 Answers

This is probably better as a comment, but since I dont have enough rep, here goes -

https://youtu.be/_JtPhF8MshA?t=219 you can see here how the recursive implementation takes space O(n) and not O(1) because the recursive tree is built all the way before they are all added and closed down!

(Note - the timestamp in the linked video shows the diagram for Fac(n) function but later ahead in the video Fib function is explained too but since there is no diagram there, this is attached)

Related