I am analyzing different ways to find the time complexities of algorithms, and am having a lot of difficulty trying to solve this specific recurrence relation by using a proof by induction.
My RR is: T(n) <= 2T(n/2) + √n
I am assuming you would assume n and prove n-1? Can someone help me out.
Let's assume T(0) = 0, T(1) = 1 (since you haven't given any trivial cases). Thus, we have: T(2) = 3.41, T(4) = 8.82, T(6) = 14.57, T(8) = 20.48, T(10) = 26.51. This seems like being a linear function.
So, we could assume T(n) <= C * n + o(n).
This can be proven by induction. Suppose T(k) <= C*(k) + o(k) = C*(k) + o(n). for each k<n.
We should prove T(n) <= C*n + o(n).
Using the recurrence, T(n) <= 2*T(n/2) + sqrt(n) <= 2*(C*(n/2) + o(n)) + sqrt(n) = C*n + (2*o(n) + sqrt(n)) = C*n + o(n).
Thus, we have proven T(n) <= C*n + o(n), which guarantees that T(n) is at least O(n).
Also, it can be shown that the solution of T(x) = 2T(x/2) + sqrt(x), T(0)=0, T(1)=1 is T(x) = (2x-sqrt(2x))/(2-sqrt(2)).