Improvement of Time Complexity and Space on Optimal Binary Search Trees using post dynamic Programming Methodology and Data Preprocessing - Hrushikesava Raju, S; Nagabhusana Rao, M (International Journal of Computer Sciences and Engineering, 2025)
There are various methods of handling Optimal Binary search trees in order to improve the performance. One of the methods is Dynamic programming which incurs O(n3) time complexity to store involved computations in a table. The data mining technique called Data Preprocessing is used in order to remove noise early in the dataset and enhances consistency of the given data. The post dynamic computing is applied using knowledge of dynamic programming principle which starts with only required data and computes only the necessary attributes required to construct Optimal Binary Search Tree with time complexity O(n) if there are n identifiers / integers / any complex objects. This approach avoids computing all necessary table attributes. Hence, the complexity or cost of post dynamic computing using Dynamic Programming is proven to be less than O(n3) or even less than specified in some cases with experimental results.