I am try to find the solution to the recurrence T(n) = T (n-1) + T(n/2) + 1
Whats I have done:
T(n) = 2T(n-1 + n/2) + 1 T(n) = 2T(2n/2 - 2/2 + n/2) +1 T(n) = 2 T((3n - 1)/2) +1 if U(X) = T(x/3 + 1) then: U(X) = 2U(x/2) U(X) = x T(n) = 3(N - 1) + 1
This makes any sense ?
Edit: The context is computer science, so when you divide n/2 and n odd you get the next inferior natural number (e.g 1/2 -> 0)