Complexity Analysis of GPA and GPA-ES Algorithms for Symbolic Regression

Abstract

This paper presents a complexity analysis of Genetic Programming (GP) for Symbolic Regression. Two algorithms, classic GPA and the hybrid method GPA + ES, are introduced and then compared. First, the implementations and properties of these methods are described. Results indicate that both algorithms have exponential time and space complexity, with GPA + ES not being asymptotically less demanding than GPA. However, polynomial complexity is achievable when certain parameters are set as constants. This analysis offers insights into algorithm performance and applicability, particularly for analyzing large datasets.