Recursive Function Complexity

[oleg9419]

I have a function T(n) = T(n-1) + T(n-2) + T(n-3) + 8 and T(1) = 1
I need to calculate its run-time.

My idea : Approximation Method

Worst Case :
I say that T(n-3) will be (as slow as) T(n-1)
T(n-3)=T(n-1)
T(n-2)=T(n-1)

so
T(n) = 3*T(n-1) + 8
T(n-1) = 3*T(n-2) + 8
T(n-2) = 3*T(n-3) + 8
Substituting back : T(n) = 27*T(n-3) + 104 so

T(n) = 3^k*T(n-k) + 104

n-k = 1 and n = k

Result :

T(n) = 3^n*1 + 104

I'm sure 104 must not be here

Best Case
I say that T(n-1) will be (as fast as) T(n-3)
T(n-1)=T(n-3)
T(n-2)=T(n-3)

so
T(n) = 3*T(n-3) + 8
T(n-3) = 3*T(n-3) + 8
T(n-6) = 3*T(n-9) + 8
Substituting back : T(n) = 27*T(n-9) + 104 so

T(n) = 3^k*T(n-3*k) + 104

n-3*k = 1 and n = 3*k+1 and k = (n-1)/3

Result :

T(n) = (3^(n-1)/3)*1 + 104

Again I'm sure 104 must not be here

so my Result must be between these 2 cases , so I say

O(T(n))=3^n 

About that 104 nr, when substituting back I noticed this growth : first 8, then 32 and then 104 so no kind of series for me... I can't write it as
formula with "k".


Please let me know if any step is false :)

thank you

[MiiNiPaa]

Yes, it is 3^n. In your case even experimental analysis will show that: http://digital.cs.usu.edu/~allanv/cs5050/W2Handout.pdf (in the end)

Master method gives 3^n too http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html

[oleg9419]

MiiniPaa thank you .

I know it's tough work but will you please tell me if my logic was correct or I got it wrong ?
I'm glad I got 3^n but I would like to be more exact ( I'm sure the professor won't give me many points for that kind of solving)