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!

enter image description here


marked as duplicate by fade2black, Evil, David Richerby, Juho, Andrej Bauer Nov 11 '17 at 14:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This kind of question should be covered by the already mentioned reference question as well as many others I would think. $\endgroup$ – Guildenstern Nov 7 '17 at 13:06
  • 2
    $\begingroup$ Sorry, but your screen grab is barely legible. Please don't use images to represent text. Also, note that recurrence relations don't have complexities and the screen grab isn't a recurrence relation. $\endgroup$ – David Richerby Nov 7 '17 at 18:34
  • $\begingroup$ The screen shot was of the same quality that my instructor provided, and the recurrence is in line 8 when it calls func4. Thanks David. $\endgroup$ – christina Nov 7 '17 at 19:06
  • $\begingroup$ also thanks so much for the clear answers, I know EXACTLY what to do now $\endgroup$ – christina Nov 7 '17 at 19:07
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – D.W. Nov 11 '17 at 2:25

The first step is to solve the easier recurrence $$ T(n) = T(n-4) + T(n-10). $$ This is explained in our reference question. The solution to your recurrence will likely be larger by a factor of $\log n$, roughly speaking.

Indeed, you can consider a recursion tree in which the root is $n$, and a node $m$ has children $m-4$ and $m-10$ (you stop the recursion at some constant $m$). The solution to the recurrence $T(n) = T(n-4) + T(n-10)$ is proportional to the number of leaves, which we expect to be proportional to the number of nodes. For all $m \geq \sqrt{n}$ (say), $\log n = \Theta(\log m)$, which leads us to expect that the solution of your non-homogeneous recurrence is larger by a factor of $\log n$ than the solution of the corresponding homogeneous recurrence $T(n) = T(n-4) + T(n-10)$.

The preceding paragraph contains some intuition which will need to be proven. But whether or not the $\log n$ factor appears in the final formula makes little difference, since the growth rate of the recurrence is exponential.


Not the answer you're looking for? Browse other questions tagged or ask your own question.