0

I need help with the following recurrence relation.

T(1) = 1

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

This is what I've tried. I think I might have messed up the substitution part but again please take a look at let me know if the time complexity I've got is correct.

T(n) = T(n-1)*n               T(n-1) = T(n-2)*n-1
T(n) = [T(n-2)*(n-1)]*n
T(n) = T(n-2)*(n-1)*n
T(n) = [T(n-3)*n-2]*(n-1)*n
T(n) = T(n-3)*(n-2)*(n-1)*n
...
...
...
T(n) = T(n-k)*(n-(k-1))*(n-(k-2))...*(n-1)*(n)

Assuming n-k=0, n=k

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

O(n^2)

Now I am not sure if what I did was exactly correct or not but any help would be appreciated.

Community
  • 1
  • 1
user372204
  • 69
  • 2
  • 10

2 Answers2

2

Only the final complexity is wrong, you end up with O(n!).

The recursive relation must be T(n) = T(n-1)+n for getting O(n^2) as the complexity.

gany_15
  • 66
  • 1
  • 4
1

Very close! You've correctly identified that the complexity is

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

However, that's not O(n2). It would be O(n2) if you added the terms rather than multiplying them.

What do you call the product of all the natural numbers from 1 to n, inclusive?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065