ABSTRACT

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 to remove noise early in the data and enhance consistency of given data. The data postcomputing (opposite to Data Preprocessing) is applied using 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 table attributes. Hence, the complexity or cost of Data post computing using Dynamic Programming is proved to be less than O(n3) or even less than specified in some cases with experimental results.