This question already has an answer here:
I'm trying to understand how to find the asymptotic complexity of a linear recurrence relation. So far, what I understand is that if only one linear recurrence call is made (ex. cn + T(n-4)), substitution or the recurrence tree can be used. However, what should one do if there are 2 or more linear recurrence calls? For the example I got in class (shown below), I got that T(n) = T(n-4) + logn + T(n-10). I tried setting a lower bound of T(n)> log n + 2T(n-10) since that's how we solved Fibbonacci Numbers, but I wound up with a complex summation that I could not solve. Any help is appreciated, thank you!