Geodesic
Mathematical Methods for the Analysis of Recursive Algorithms
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 1 (2008) no. 3, pp. 236-246.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{JSFU_2008_1_3_a1,
     author = {Valentina V. Bykova},
     title = {Mathematical {Methods} for the {Analysis} of {Recursive} {Algorithms}},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {236--246},
     publisher = {mathdoc},
     volume = {1},
     number = {3},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2008_1_3_a1/}
}
TY  - JOUR
AU  - Valentina V. Bykova
TI  - Mathematical Methods for the Analysis of Recursive Algorithms
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2008
SP  - 236
EP  - 246
VL  - 1
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2008_1_3_a1/
LA  - ru
ID  - JSFU_2008_1_3_a1
ER  - 
%0 Journal Article
%A Valentina V. Bykova
%T Mathematical Methods for the Analysis of Recursive Algorithms
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2008
%P 236-246
%V 1
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2008_1_3_a1/
%G ru
%F JSFU_2008_1_3_a1
Valentina V. Bykova. Mathematical Methods for the Analysis of Recursive Algorithms. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 1 (2008) no. 3, pp. 236-246. http://geodesic.mathdoc.fr/item/JSFU_2008_1_3_a1/

[1] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Struktury dannykh i algoritmy, Vilyams, M., 2007

[2] D. Grin, D. Knut, Matematicheskie metody analiza algoritmov, Mir, M., 1987 | MR

[3] R. Grekhem, D. Knut, O. Potashnik, Konkretnaya matematika, Mir, Binom. Laboratoriya znanii, M., 2006

[4] S. K. Lando, Lektsii o proizvodyaschikh funktsiyakh, MTsNMO, M., 2004

[5] V. N. Sachkov, Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982 | MR | Zbl

[6] V. A. Goloveshkin, M. V. Ulyanov, Teoriya rekursii dlya programmistov, Fizmatlit, M., 2006

[7] Kormen, Ch. Lezerson, R. Rivest, Algoritmy: postroenie i analiz, MTsNMO, M., 1999

[8] V. V. Bykova, Diskretnaya matematika s ispolzovaniem EVM, KrasGU, Krasnoyarsk, 2006

[9] V. V. Bykova, “Asimptoticheskaya otsenka slozhnosti rekursivnykh algoritmov s additivnym umensheniem razmernosti zadachi”, Trudy shestoi Vserossiiskoi FAM' 2007, Ch. 2, Grotesk, Krasnoyarsk, 2007, 17–25

[10] G. Korn, T. Korn, Spravochnik po matematike, Nauka, M., 1973