It is considered as a careful bruteforce. And interestingly we will get it in polynomial time.What it does is divide the problem into sub problem and solve the same and reuse the same for larger problem.
Lets take the example of fibonacci number !!
F(n) :
if(n <= 2) :
f = 1;
else :
f = f(n-1)+f(n-2);
return f;
|
Looks like neat !! But it is not because it running in an exponential time, because each time recalculating many functions.
Eg : F(4) :
f = [ F(3) + F(2) ]
= [ F(2) + F(1) ] + 1
= [ 1 + 1 ] + 1
= 2 +1
= 3
Here we can see that F[2] is calculated 2 times. Like that there may be many situations where we are recalculating.
Proof exponential time :
T(n) = T(n-1) + T(n-2)+ O(1)
> 2T(n-2)
= O(2^(n/2))
