Facebook Interview Question Software Engineer / Developers
Linear time and constant for storage.
fibonacci(n)
{
int x2 = 0;
int x1 = 1;
int x;
if (n == 0) return 0;
for(int i = 2; i <n; i++)
{
x = x2 + x1;
x2 = x1;
x1 = x;
}
return x2+x1;
}
In case of plain-old recursion time complexity is O(2^n) and space complexity is O(n). In case of DP both time and space are O(n).
Note that these complexities are expressed in the value of n and not in the length (number of bits) of n. So O(2^n) is exponential and all the other O(n) complexities are pseudo-polynomial.
In short, it doesn't matter how you implement it, both time and space complexities are exponential. ;)
Time complexity is O(n)
space complexity: total space used by all,recursive calls : O(n)
fibo(1) and fibo(0) is base case
fibo(3)= fibo(2)+fibo(1) -->2 calls
we need space for local variables and function arguments, but also some space for remembering where each call should return to.The argument at each node in the path is ONE(1) or TWO(2) units smaller than the argument at its PARENT(3). The length of any such path can be at most n, so the space needed by the recursive algorithm is again (some constant factor times) n.
0, 1, 1, 2, 3, 5, 8, 13, ...
fib(2) = fib(0) + fib (1) // 1 + 1 + 1 = 3 = 2^1 + 1
fib(3) = fib(1) + fib (2) // 1 + 3 + 1 = 5 = 2^2 + 1
fib(4) = fib(2) + fib(3) // 3 + 5 + 1 = 9 = 2^3 + 1
hence fib(n) - recursive calls = 2^(n-1) + 1
ie. O(2^n) - which is exponential complexity. Looking at the space in similar fashion for each recursive call - we get O(n)
but when it comes to fib(5)
fib (5) = fib (3) + fib (4) = 5 + 9 + 1 = 15
it isn't 2^4 + 1 = 17 and less than it.
Why dont you people try recursion as dynamic programming and make it linear :D
- Anonymous September 28, 2011