## 8 Complexity Analysis of the Proposed Approach  
A detailed complexity analysis is presented in this section. The complexity of the LOA depends on the following parameters: population size (N), number of iterations (T), and fitness evaluation (F) for each individual in the population.  
1. **Lyrebird Optimization Algorithm:** 1. **Time Complexity:** 2. **Population Initialization:** Randomly generating an initial population requires O(N), where N is the population size.
2. **Fitness Calculation:** For each iteration, the fitness of each individual is evaluated. Let the fitness evaluation take O (F). So, for each iteration, it takes O (N \(\times\) F).
3. **Exploration and Exploitation (Search Process):** For each iteration, the algorithm applies search mechanisms (exploitation and exploration) on the population. Since each individual is updated per iteration, it contributes to an additional O (N) per iteration.
4. **Overall Time Complexity of the LOA:** O (T \(\times\) N \(\times\) F), where \(T\) is the number of iterations, \(N\) is the population size, and \(F\) is the time complexity for fitness calculation.
5. **Space Complexity of the LOA:** 1. **Population storage:** Each individual in the population is stored, so the space complexity is O (N).
6. **CatBoost Classifier:** The complexity of CatBoost depends on the following: Number of trees (T), maximum depth of trees (D), number of data points (n), and number of features (f). 2. **Time Complexity of CatBoost:** 3. **Tree Construction:** The complexity of building one tree in CatBoost is O(n \(\times\) f \(\times\) D), where \(n\)-n is the number of data points, \(f\)-f is the number of features, and D is the maximum depth of the trees. 4. **Total Time Complexity:** With \(T\) trees, the overall time complexity for CatBoost is O(T \(\times\) n \(\times\) f \(\times\) D).
7. **Space Complexity of CatBoost:** 4. **Model Storage:** CatBoost needs to store the trees, so the space complexity is O(T \(\times\) n \(\times\) D).  
To ensure the efficiency of the proposed approach, let us compare the computational complexity with Gboost [31]. Let us breakdown the time and space complexity of GBoost and investigate how CatBoost improves on it in terms of reducing overfitting, using ordered target statistics, and its balanced tree structure.  
The time complexity of Gboost is given by O (T \(\times\) n \(\times\) f \(\times\) log n), where T is the number of trees in the model; \(n\) is the number of data points or samples;\(f\) is the number of features or columns in the dataset; and log \(n\) represents the complexity of sorting the data at each node split. XGBoost builds decision trees iteratively. At each split of the decision tree, the algorithm selects the best feature that minimizes a loss function (like mean squared error for regression tasks). The process of finding the best feature and its splitting point requires sorting the feature values for each node in the tree, which costs O (log n). Since XGBoost builds \(T\) trees, and for each tree, it looks through all n data points and \(f\) features to find the best split, and the total time complexity becomes O (T \(\times\) n \(\times\) f \(\times\) log n). The space complexity of Gboost is given by O (T \(\times\) n \(\times\) D), where D is the maximum depth of the trees. Each tree stores information for all \(n\) samples, and since XGBoost constructs \(T\) trees, the overall space required for storing the tree structure and the data associated with each node is O (T \(\times\) n \(\times\) D).