Search code examples
big-orecurrence

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

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

Solution

  • 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))