Order by Recursion tree

Question

I have tried determining the running time given by a recurrence relation, but my result is not correct.

Recurrence

T(n) = c + T(n-1) if n >= 1
     = d          if n = 0

My attempt

I constructed this recursion tree:

                   n
                   |
                  n-1
                   |
                  n-2
                   |
                  n-3
                   |
                  n-4
                   |
                  n-5
                   |
                   |
                   |
                   |
                   |
                   |
                Till we get 1

Now at level i, the size of the sub problem should be, n-i

But at last we want a problem of size 1. Thus, at the last level, n-i=1 which gives, i=n-1.

So the depth of the tree becomes n-1 and the height becomes n-1+1= n.

Now the time required to solve this recursion = height of the tree*time required at each level which is :

n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+ ...
==> (n+n+n+n+n+ ... )-(1+2+3+4+5+ ... )
==> n - (n(n+1)/2)

Now the time taken = n* ((n-n2)/2) which should give the order to be n², but that is not the correct answer.

Answer 1

Now at level i, the size of the sub problem should be, n-i

Yes, that is correct. But you're assuming, that the runtime equals the sum of all the subproblem sizes. Just think about it, already summing the first two levels gives n + (n - 1) = 2n - 1, why would the problem size increase? _{Disclaimer: A bit handwavy and not an entirely accurate statement.}

What the formula actually says

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

The formula says, solving it for some n takes the same time it takes to solve it for a problem size that is one less, plus an additional constant c: c + T(n - 1)

Another way to put the above statement is this: Given the problem takes some time t for a certain problem size, it will take t + c for a problem size, that is bigger by one.

We know, that at a problem size of n = 0, this takes time d. According to the second statement, for a size of one more, n = 1, it will take d + c. Applying our rule again, it thus takes d + c + c for n = 2. We conclude, that it must take d + n*c time for any n.

_{This is not a proof. To actually prove this, you must use induction as shown by amit.}

A correct recursion tree

Your recursion tree only lists the problem size. That's pretty much useless, I'm afraid. Instead, you need to list the runtime for said problem size.

Every node in the tree corresponds to a certain problem size. What you write into that node is the additional time it takes for the problem size. I.e. you sum over all the descendants of a node plus the node itself to get the runtime for a certain problem size.

A graphical representation of such a tree would look like this

Tree        Corresponding problem size
c                                    n
|
c                                    n - 1
|
c                                    n - 2
|
c                                    n - 3
.
.
.
|
c                                    2
|
c                                    1
|
d                                    0

Formalizing: As already mentioned, the label of a node is the additional runtime it takes to solve for that problem size, plus all its descendants. The uppermost node represents a problem size of n, bearing the label c because that's in addition to T(n-1), to which it is connected using a |.

In a formula, you would only write this relation: T(n) = c + T(n-1). Given that tree, you can see how this applies to every n>=1. You could write this down like this:

T(n)     = c + T(n - 1) # This means, `c` plus the previous level
T(n - 1) = c + T(n - 2) # i.e. add the runtime of this one to the one above^
T(n - 2) = c + T(n - 3)
...
T(n - (n - 2)) = c + T(1)
T(n - (n - 1)) = c + T(0)
T(0) = d

You can now expand the terms from bottom to top:

T(n - (n - 1)) = c + T(0)
T(0) = d

T(n - (n - 2)) = c + T(1)
T(n - (n - 1)) = c + d
T(0) = d

T(n - (n - 3)) = c + T(2)
T(n - (n - 2)) = c + (c + d)
T(n - (n - 1)) = c + d
T(0) = d

T(n - (n - 4)) = c + T(3)
T(n - (n - 3)) = c + (2*c + d)
T(n - (n - 2)) = c + (c + d)

...

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

T(n) = c + (n-1)c + d = n*c + d
T(n - 1) = (n-1)c + d

Summing 1 to n

n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+ ...
==> (n+n+n+n+n+ ... )-(1+2+3+4+5+ ... )
==> n - (n(n+1)/2)

From the first line to the second line, you have reduced your problem from summing 1 to n to, well, summing 1 to n-1. That's not very helpful, because you're stuck with the same problem.

I'm not sure what you did on the third line, but your transition from the first to the second is basically correct.

This would have been the correct formula:

Answer 2

T(n) = c + T(n-1) 
     = c + (c + T(n-2)) 
     = ... 
     = c*i + T(n-i) 
     = ...
     = c*n + T(0)
     = c*n + d

If we assume c,d are constants - it gets you O(n)

To prove it mathematically - one can use mathematical induction

For each k < n assume T(n) = c*n + d
Base is T(0) = 0*n + d = d, which is correct for n < 1

T(n) = c + T(n-1)               (*)
     = c + (n-1)*c + d 
     = c*n + d

(*) is the induction hypothesis, and is valid since n-1 < n

Answer 3

The complexity would be O(n).

As you described the functions converts the problem for input n into problem for (n-1) by using a constant operation 'c'.

So moving down the recursion tree we will have in total n levels, and at each step we require some constant operation 'c'.

So there will be total c*n operations resulting into the complexity O(n).