Solving recurrence T(n) = T(n - 1) T(n - 2) T(n

I have a backtracking algorithm. The running time is given by below relation:

T(n) = T(n - 1) T(n - 2) T(n - 3) T(n - 4) ... T(1)

T(1)=1

What would be the worst time complexity of this algorithm? Intuitively it looks O(n^n) to me. But I may be wrong. How to calculate it formally?

CodePudding user response：

Here's a simple way: You could calculate the time complexity by expanding each of the additive terms and observe the pattern:
T(n)
= T(n-1) T(n-2) T(n-3) ... T(1)
= (T(n-2) T(n-3) ... T(1)) T(n-2) T(n-3) ... T(1)
= 2T(n-2) 2T(n-3) ... 2T(1)
= 4T(n-3) ... 4T(1)
= 2^(k-1) T(n-k) ... 2^(k-1) T(1)
= 2^(n-2) T(1)
= 2^(n-2)

CodePudding user response：

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

Thus T(n) = c * 2^n, where c is T(1)/2.

CodePudding user response：

You have the following:

T(1) = 1
T(2) = T(2-1) = T(1) = 1
T(3) = T(3-1)   T(3-2) = T(2)   T(1) = 2
T(4) = T(4-1)   T(4-2)   T(4-3) = T(3)   T(2)   T(1) = 2   1   1 = 4
T(5) = 4   2   1   1 = 8
T(6) = 8   4   2   1   1 = 16
...

From the above it follows by induction that T(n) = 2*T(n-1) with the base cases T(1) = T(2) = 1

We can further built on this saying that since T(n) = 2*T(n-1), T(n) = 2*2*T(n-2). It follows that T(n) = (2^i)*T(n-i) for i < n-2 and n > 2.

So in terms of time complexity we get O(2^n).

Note: Please correct me if I'm wrong. I'm not the very best with this stuff. My appologies in advance. I'm trying to learn myself.