- Issue
- Journal of Siberian Federal University. Mathematics & Physics. 2008 1 (3)
- Authors
- Bykova, Valentina V.
- Keywords
- complexity of algorithms; recursion; recurrent relations
- 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.
- Pages
- 236-246
- Paper at repository of SibFU
- https://elib.sfu-kras.ru/handle/2311/772
Journal of Siberian Federal University. Mathematics & Physics / Mathematical Methods for the Analysis of Recursive Algorithms
Full text (.pdf)