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!

回答1:

Yes, you are correct:

T(n) = n^c + (n-1)^c + (n-2)^c + … + 3^c + 2^c + 1,

and this sum is

T(n) = O(n^c+1). See e.g. Faulhaber's formula. In fact, you can even determine the constant in the leading term (even if it's not germane to the algorithm's asymptotics): the sum is n^c+1/(c+1) + O(^c), as you can determine through e.g., using, say, integration.

回答2:

What you have is not correct, but you were on the right track.

The mistake you made:

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 

You cannot just go from the first line to the second line.

As you increase k, the number of terms in the right hand side increases too.

To see that think of writing it this way:

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

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

T(n-k) - T(n-k-1) = (n-k)^c.

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

What happens if you add these up?

Once you do that, can you see what the answer will be for c=1 and c=2? Can you figure out a pattern for the final answer from there?

回答3:

Instead of working you way down from n, how about start by working your way up from 0 (I assume the recursion terminates at 0 and you left that bit out). When you start noticing a fixed point (ie a pattern which repeats the same in all cases) you have a good candidate for an answer. Try proving the answer, e.g. through induction.

回答4:

I would start by observing that n^c, whilst of course influenced by the value of n, is not going to be any more complex for n vs. n + 1 - it's c that determines the "runtime" of that particular term. Given that, you can assume (at least I would) that the term has constant runtime and determine how many times the recursion will execute for a given n and you'll get your bound.

回答5:

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.

回答6:

Here it is:

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

which is O(n^c+1).

To show this is a reasonable bound, note that when c = 1,

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

which is clearly Θ(n²).