Recurrences in Computational Complexity
Manish Sharma asked me an interesting question over chat regarding recurrences and computational complexity estimation. The question was interesting enough that I thought that the answer would be of use to many more people in general so I'm posting it to my blog. In any case, a post to my blog was long overdue. So, here it is: The original question was: How do you find the computational complexity of the recurrence: T(n) = a.T(n . r) + b.T(n (1 - r)) + O(n) or, when pretty printed: Well, technically speaking, this question is phrased slightly ambiguously, so I'm phrasing it as below: T(n) = a T(n r) + b T(n (1-r)) + cn + d a > 0, b > 0, c > 0, d belonging to R Pretty print: and while I'm at it, I'll point out to you that without loss of generality, I can impose the additional restriction that r is in the range of 0.5 to 1.0. Pretty print: This is possible because I can simply take a recurrence equation where this isn't true and ...