Search code examples
recurrencebig-o

How to solve the following recurrences and find a Theta bound

  1. T(n) = T(n-1)+n^c
  2. T(n) = T(n-1)+c^n

where c is a constant

Solution

  • If you unroll the recursion, for the first case you will get:

    1^c + 2^c + ... + (n-1)^c + n^c

    which is a Faulhaber's formula. It tells you that the complexity is O(n^(c+1))

    The second one is:

    c^1 + c^2 + ... + c^(n-1) + c^n

    which is the sum of geometrics and O(c^n)