RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



J. Sib. Fed. Univ. Math. Phys.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


J. Sib. Fed. Univ. Math. Phys., 2008, Volume 1, Issue 3, Pages 236–246 (Mi jsfu23)  

This article is cited in 7 scientific papers (total in 7 papers)

Mathematical Methods for the Analysis of Recursive Algorithms

Valentina V. Bykova

Institute of Mathematics, Siberian Federal University

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.

Full text: PDF file (309 kB)
References: PDF file   HTML file

UDC: 519.6
Received: 05.03.2008
Received in revised form: 10.04.2008
Accepted: 05.05.2008

Citation: Valentina V. Bykova, “Mathematical Methods for the Analysis of Recursive Algorithms”, J. Sib. Fed. Univ. Math. Phys., 1:3 (2008), 236–246

Citation in format AMSBIB
\Bibitem{Byk08}
\by Valentina~V.~Bykova
\paper Mathematical Methods for the Analysis of Recursive Algorithms
\jour J. Sib. Fed. Univ. Math. Phys.
\yr 2008
\vol 1
\issue 3
\pages 236--246
\mathnet{http://mi.mathnet.ru/jsfu23}


Linking options:
  • http://mi.mathnet.ru/eng/jsfu23
  • http://mi.mathnet.ru/eng/jsfu/v1/i3/p236

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. V. Bykova, “Elastichnost algoritmov”, PDM, 2010, no. 2(8), 87–95  mathnet
    2. V. V. Bykova, “Elastichnost algoritmov”, PDM, 2010, prilozhenie № 3, 76–78  mathnet
    3. Valentina V. Bykova, “Analysis parameterized algorithms on the bases of elasticity to functions complexity”, Zhurn. SFU. Ser. Matem. i fiz., 4:2 (2011), 195–207  mathnet
    4. V. V. Bykova, “FPT-algoritmy i ikh klassifikatsiya na osnove elastichnosti”, PDM, 2011, no. 2(12), 40–48  mathnet
    5. V. V. Bykova, “FPT-algoritmy na grafakh ogranichennoi drevovidnoi shiriny”, PDM, 2012, no. 2(16), 65–78  mathnet
    6. V. V. Bykova, “Ob asimptotike reshenii rekurrentnykh sootnoshenii v analize algoritmov rasschepleniya dlya propozitsionalnoi vypolnimosti”, PDM. Prilozhenie, 2013, no. 6, 112–116  mathnet
    7. V. V. Bykova, “Ob asimptotike reshenii rekurrentnykh sootnoshenii spetsialnogo vida i tekhnike Kulmana–Lyukkhardta”, PDM, 2013, no. 4(22), 56–66  mathnet
  • Журнал Сибирского федерального университета. Серия "Математика и физика"
    Number of views:
    This page:1510
    Full text:460
    References:139

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018