solving recurrence T(n) = T(n/2) + T(n/2 - 1) + n/2 + 2

Question

Need some help on solving this runtime recurrence, using Big-Oh:

T(n) = T(n/2) + T(n/2 - 1) + n/2 + 2

I don't quite get how to use the Master Theorem here

Answer 1

For n big enough you can assume T(n/2 - 1) == T(n/2), so you can change

  T(n) = T(n/2) + T(n/2 - 1) + n/2 + 2

into

  T(n) = 2*T(n/2) + n/2 + 2

And use Master Theorem (http://en.wikipedia.org/wiki/Master_theorem) for

  T(n) = a*T(n/b) + f(n)

  a = 2
  b = 2
  f(n) = n/2 + 2
  c = 1 
  k = 0

  log(a, b) = 1 = c 

and so you have (case 2, since log(a, b) = c)

  T(n) = O(n**c * log(n)**(k + 1))
  T(n) = O(n * log(n))