Talk:Prune and search

This equation is only true for some cases, for example, it would show binary search as taking O(1). The following is a more thorough equation which I would put in, but I don't know how to do the notation:

T(n) = a*T(n/b) + theta O(n^k)

The solution where a >=1 and > 1 is the piecewise function:

O(n^k * log n), if a = b^k O(n^(log base b of a)), if a > b^k O(n^k), if a < b^k

Fixing recurrence relation solution

I solved the recurrence relation with the Akra-Bazzi method. If it can be generally solved, with little or no assumptions over S(n), please edit and remove the link to Akra-Bazzi method. Anyway the previous equation must be fixed, since it is not generally true. I see the point about using a 1998 method to solve a 1983 relation, still the Akra-Bazzi method is used only because it can solve the equation with one simple and very clear assumption over S(n). I suggest that the recurrence relation is either left unsolved or solved the way I proposed.Andreaf96 (talk) 23:18, 24 March 2016 (UTC)

The textbook method for solving this is by a geometric series. Attaching someone else's name who published about more general recurrences in 1998 (when this method was known for much longer) seems to be an example of making things more difficult, not simpler. And the only point of Akra–Bazzi is to handle recurrences that divide the problem into multiple subproblems of different sizes, but here there is only one subproblem. So you could also use the master theorem, but the additional complication of Akra–Bazzi is pointless obfuscation. —David Eppstein (talk) 00:14, 25 March 2016 (UTC)

If we chose p = 1/2 and S(n) = O(1), we have T(n) = O(1) + T(n/2), which is the recurrence relation for binary search. If we accept the solution given in the page, we get T(n) = O(1), but we all know that the true solution of that recurrence relation is T(n) = O(log n). The only reason I used the Akra-Bazzi method is because S(n) can be any function, so the only way to solve the recurrence relation for (almost) every S(n) is by the Akra-Bazzi method.Andreaf96 (talk) 11:59, 25 March 2016 (UTC)

I merged the two solutions, reusing David Eppstein contribute. Hope this will be accepted. Andreaf96 (talk) 14:01, 25 March 2016 (UTC) I see the remark David Eppstain made, and agree with him. His last edit solves the problem to me. — Preceding unsigned comment added by Andreaf96 (talk • contribs) 16:02, 25 March 2016 (UTC)