Doubt : Recurrence Relation.

Question

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

hints :

define R(n) = T(n)/(n-1)!

solve the recurrence for R(n)

express T(n) as a function of R(n)

 

How to proceed , i am not getting it ?

Can i reduce it to the form so that i can use masters theorem.

Comments

@OneZero 

1. Explain the recurrence solution.

2. 2nd one is actually post on anothet question i have posted, i mistakenly commented here. 

Anyways, excuse and explain your O(n!) approach.

---

@HeadShot

 

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

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

hence T(n) = T(n-2)*(n-2)*(n-1) + (n-1) + 1

T(n-2) = T(n-3)*(n-3) + 1

hence T(n) = T(n-3)*(n-3)*(n-2)*(n-1) + (n-2)*(n-1) + (n-1) + 1

in general T(n) = T(n-k)*(n-k)*(n-(k-1))* ..... *(n-1) 

                            + (n-(k-1))* .... *(n-1)

                            ......

                            + (n-1)

because the terminating condition was not given, i assumed n-k = 1

hance k = n-1

therefore T(n) = 1*2*3*....*(n-1)

                          + 2*3*......*(n-1)

                          + 3*4*.....*(n-1)

                          ......

                          + (n-1)

T(n) = (n-1)P1 + (n-1)P2 + ...... + (n-1)P(n-2)

T(n) = (n-1)!*e (approx)

hence T(n) = O(n!)

 

---

The value of the recurrence relation will change like this.

n | T(n)
0 | 1
1 | 1
2 | 2
3 | 5
4 | 16
5 | 65
6 | 326
7 | 1957
8 | 13700
9 | 109601