Solve: T(n)=T(n-1)+T(n/2)+n.
I tried solving this using recursion trees.There are two branches T(n-1)
and T(n/2)
respectively. T(n-1)
will go to a higher depth. So we get O(2^n)
. Is this idea correct?
This is a very strange recurrence for a CS class. This is because from one point of view: T(n) = T(n-1) + T(n/2) + n
is bigger than T(n) = T(n-1) + n
which is O(n^2).
But from another point of view, the functional equation has an exact solution: T(n) = -2(n + 2)
. You can easily see that this is the exact solution by substituting it back to the equation: -2(n + 2) = -2(n + 1) + -(n + 2) + n
. I am not sure whether this is the only solution.
Here is how I got it: T(n) = T(n-1) + T(n/2) + n
. Because you calculate things for very big n
, than n-1
is almost the same as n
. So you can rewrite it as T(n) = T(n) + T(n/2) + n
which is T(n/2) + n = 0
, which is equal to T(n) = - 2n
, so it is linear. This was counter intuitive to me (the minus sign here), but armed with this solution, I tried T(n) = -2n + a
and found the value of a.