The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
F(n) = F(n-1) + F(n-2)
with seed values
F(0) = 0 and F(1) = 1.
Note: The seed values can be changed as per requirements of the user but the standard values are the ones mentioned above.
Space Complexity of an algorithm depends upon : Input Size + Extra space (including variables, stack, array etc)
Fibonacci series using Recursion:
a)Divide and Conquer Programming
b)Dynamic Programming
a) Divide and Conquer Programming
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
Above is the Recursive tree for n=5 elements, the Function calling is also shown in above diagram.
Function calling in a recursive function is PREORDER TRAVERSAL
Function execution in a recursive function is POSTORDER TRAVERSAL
Every Recursive program requires Stack data structure to store the recursive calls .
To find the space required by the stack depends upon the depth of the stack by function calling which inturn depends on number of levels in a tree.
Now, left child of every node is decremented by 'n-1' at each level until it reaches the termination condition.
and right child of every node is decremented by 'n-2' at each level until it reaches the termination condition.
Now, For worst case More the number of levels more is the space required for function calling.
Observe, Left side of the tree contains maximum function calls are decremented by 'n-1' at each level and will reach the termination condition with more number of levels as compared to right side.
considering the worst case assume the above binary tree to be complete binary tree, now the maximum number of levels will be O(n)
Therefore , 'n' element stack size is required for function calling.
Now Space complexity : Input size = O(n) + Extra = ( 1 variable + Stack size = n)
Space Complexity becomes O(n).
b)Using Dynamic Programming : It is a technique to reduce the time complexity of Fibonacci series from O(2n) to O(n).
In case of Dynamic programming, Function calling will be same but the values are stored once a distinct function is executed and the values will be retrieved if the same function calls again.
Observe the above diagram there are many functions which are repeating somewhere, One can find the distinct problems
that are to be solved are only = fib(5) , fib(4) , fib(3) , fib(2) , fib(1) , fib(0).
We use a table i.e an array to store these distinct functions and the size of array also plays important part in space complexity.
Now for n = 5 , there are 5 distinct functions, that means , for fib(n) = there are 'n' distinct functions that are to be stored in array
Space Complexity = Input size = O(n) + Extra ( Stack = O(n) and Array = O(n))
Space complexity becomes O(n).
Fibonacci without recursion :
int n, first = 0, second = 1, next, c;
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d\n",next);
}
This does not require any recursive call no data structure is required therefore the Space Complexity is very very less as compared to Recursive algorithm
Space Complexity = Input Size = O(n) + Extra = O(1) constant only
There fore Space Complexity becomes O(n) . But will be very very less as compared to recursive algorithm.
Hope it helps :)
