Improvement of Time Complexity and Space on Optimal Binary Search Trees using post dynamic Programming Methodology and Data Preprocessing

Authors

  • S Hrushikesava Raju Research Scholar, Regd.No:PP.CSE.0158, Rayalaseema University,Kurnool,A.P.
  • M Nagabhusana Rao Professor, Department of CSE, K L University, Vijayawada, A.P.

Keywords:

Optimal Binary Search Tree (OBST), Data Preprocessing, Post computing, Dynamic Programming, Time Complexity

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 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.

References

. Micheline Kamber, Hei,“Data Mining: Concepts and Techniques”, Second Edition, The Morgan Kaufmann Series, ISBN 13: 978-1-55860-901-3,ISBN 10: 1-55860-901-6.

. Data Preprocessing Techniques for Data Mining, iasri.res.in/ebook/win_school_aa/notes/Data_Preprocessing.pdf

. Nguyen Hung Son, Data cleaning and data preprocessing, www.mimuw.edu.pl/~son/datamining/DM/4-preprocess.pdf

. Andy Mirzaian , DYNAMIC PROGRAMMING: OPTIMALSTATIC BINARY SEARCH TREES, http://

www.cse.yorku.ca/~andy/courses/3101/lecture-notes

/OptBST.pdf

. ROLF KARLSSON, ALGORITHM THEORY,HTTP://FILEADMIN.

CS.LTH.SE/CS/PERSONAL/ROLF_KARLSSON/LECT5.PDF

. DYNAMIC PROGRAMMING | SET 24 (OPTIMAL BINARY SEARCH TREE), HTTP://WWW.GEEKSFORGEEKS.ORG/DYNAMIC-

program ming-set-24-optimal-binary-search-tree/

. http://www.sciencedirect.com/science/article

/pii/ 0020019081901435

. E.Horotiwz, S.Sahni, Dinesh Mehta,“Fundamentals of data structures in C++” , Second Edition.

. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekharan, http://vitconference.com/vit_mca/images/resources/

DAOA/Fundamentals-of-Computer-Algorithms-

By-Ellis-Horowitz-1984.pdf

. Dynamic Programming- Optimal Binary Search Trees, http://www.radford.edu/~nokie/classes/360/dp-opt-bst.html

. Dynamic Programming, http://www.cs.utsa.edu/~bylander

/ cs3343 /chapter8handout.pdf

. optimal binary search trees, https://en.wikipedia.org/wiki/

Optimal_binary _search _tree

. Data Preprocessing, http://www.cs.ccsu.edu/~markov

/ccsu_courses/ datamining-3.html

. Data processing techniques for data mining, http://iasri.res.in/ebook/win_school_aa/notes/ Data_

Preprocessing.pdf

. Data Mining: Data and Preprocessing, http://Staffwww

.itn.liu.se/~aidvi/courses/06/dm/ lectures/lec2.pdf

. “Data Preprocessing in Data Mining” by, ISBN : 9783319102474 & 9783319102467.

. Salvadar Garcia, Julian Luengo, Francisco Hurrera , http://www.enggjournals.com/ijcse/doc/IJCSE16-

-01-009.pdf

. Efficient construction of Optimal Binary Search Trees using Data Preprocessing to improve Quality and Attribute Post computing to save Space and time through modified Dynamic Programming Technique, http://www.ijcse.net/issue.php?file=vol05issue1,40-46.

. Application of data preprocessing on given data and efficient construction of OBSTs using post dynamic Programming, http://journals.indexcopernicus.com/issue. php?id=737&id_issue=882666

Downloads

Published

2025-11-11

How to Cite

[1]
S. Hrushikesava Raju and M. Nagabhusana Rao, “Improvement of Time Complexity and Space on Optimal Binary Search Trees using post dynamic Programming Methodology and Data Preprocessing”, Int. J. Comp. Sci. Eng., vol. 4, no. 11, pp. 133–136, Nov. 2025.

Issue

Vol. 4 No. 11 (2016): IJCSE November Edition

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.