Search code examples
recurrencerelation

Recurrence Relation: Finding Big O

I am trying to find the big O bound for the following recurrence relation:

T(n) = T(n-1) + n^c, where c >= 1 is a constant

So I've decided to solve this by using iteration:

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

Suppose k = n-1, then:

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

I'm not sure if this is correct however, plus I would really appreciate some guidance as to how to derive Big O from this. Thanks a lot!

Solution

  • To figure these out, fill out a couple of terms and look for the pattern:

    T(1) = 0 + 1^c

    T(2) = T(1) + 2^c = 0 + 1^c + 2^c

    T(3) = T(2) + 3^c = 0 + 1^c + 2^c + 3^c

    T(4) = ...

    Now express the pattern in terms of n and you have your answer.