Abstract:
We prove a theorem that defines asymptotic estimates for the solution of a recurrent relation. This recurrent relation typically describes time complexity functions for recursive algorithms with an additive reduction of the dimension of a given problem. The presented results together with a known main theorem on recurrent relations give a tool for the analysis of the complexity of two most typical recursive schemes.
Keywords:complexity of algorithms, recursion, recurrent relations.
UDC:519.6
Received: 05.03.2008 Received in revised form: 10.04.2008 Accepted: 05.05.2008