Generate the Fibonacci recursively and iteratively in Java
In fibonacci series, next number is the sum of previous two numbers for example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc. The first two numbers of fibonacci series are 0 and 1.
There are two ways to generate the fibonacci series: With iteration and with recursion.
Time and Space Complexity Of Recursive and Iterative approach
The time complexity of the iterative code is linear, as the loop runs from 2 to n, i.e. it runs in O(n) time. The time taken by recursive Fibonacci is O(2^n) or exponential.
For the iterative approach, the amount of space required is the same for fib(6) and fib(100), i.e. as N changes the space/memory used remains the same. Hence it’s space complexity is O(1) or constant. The space complexity of Fibonacci recursive is O(N).
In fibonacci series, next number is the sum of previous two numbers for example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc. The first two numbers of fibonacci series are 0 and 1.
There are two ways to generate the fibonacci series: With iteration and with recursion.
Time and Space Complexity Of Recursive and Iterative approach
The time complexity of the iterative code is linear, as the loop runs from 2 to n, i.e. it runs in O(n) time. The time taken by recursive Fibonacci is O(2^n) or exponential.
For the iterative approach, the amount of space required is the same for fib(6) and fib(100), i.e. as N changes the space/memory used remains the same. Hence it’s space complexity is O(1) or constant. The space complexity of Fibonacci recursive is O(N).
No comments:
Post a Comment