Two things,
The recursive definition states that you must replace
n
withn-1
when callingT(n)
again, so your logic is sound forT(n)=T(n-3)+log(n-2)+log(n-1)+log(n)
.Your can easily make the argument that
log(1) + log(2) + log(3) + ... log(n) = log(n!) = Theta(nlogn)
, andlog(n) + log(n) + log(n) ... + log(n) = nlog(n) = Theta(nlog(n))
http://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n
http://en.wikipedia.org/wiki/Stirling%27s_approximation
To look at it as a tree, it's actually just a tree with worst case height, i.e.
This is because at each call, There is only one subproblem to solve.