Posts

Showing posts from December, 2011

Recurrences in Computational Complexity

Image
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