Base level: if(n<=1) return; data type - positive integers
I have to find the Big-Theta function of this recursive function. I've tried to develop the recursive equation but it gets complicated from level to level and no formation is seen.
I also tried this - assume that c<(1-c). so - 2T(cn) + 1 <= T(cn) + T((1-c)n)+1 <= 2T((1-c)n)+1
It gave me some lower bound and upper bound but not a theta bound :(
As c approaches either 0 or 1, the recursion approaches T(n) = T(n-1) + 2 (assuming that T(0) = 1 as well). This has as a solution the linear function T(n) = 2n - 1 for n > 0.
For c = 1/2, the recursion becomes T(n) = 2T(n/2) + 1. It looks like T(n) = 2n - 1 is a solution to this for n > 0.
This seems like strong evidence that the function T(n) = 2n - 1 is a solution for all c: it works on both ends and in the middle. If we sub in...
2n - 1 = 2cn - 1 + 2(1-c)n - 1 + 1
= 2cn - 1 + 2n - 2cn - 1 + 1
= 2n - 1
We find that T(n) = 2n - 1 is a solution for the general case.