Regular Recursion Trees: Description and Theoretical Analysis

Abstract

Recursive algorithms analysis by generated trees node counting refers to detailed study of their structures. In this connection the paper presents the specific description of peculiar to a number of recursive algorithms regular trees. We have developed the method which is based on introduced regular description and provides an analytical solution for a number of generated nodes at such regular tree each level. The results obtained make possible a theoretical time complexity analysis of recursive algorithms generating regular recursion trees.