I had a problem with recurrences complexity problems and I have found a very interesting way to solve it if the Masters Theorem can't solve it.
I mean the recurrences that look like T(x) = g(x) + Sigma(from i = 1 to k, ai * T(bi*x + hi(x) ) for x>=x0.
The Akra-Bazzi Method solves it and you can obtain what you need in a fast and elegant way.
Here is the Masters Theorem for recurrences like T(x) = g(n) + a*T(x/b) if you need.
No comments:
Post a Comment