Simulation Expirment for Proofing the Theoretical As-sumption of Time Complexity for Binary Search Tree | ||
| Ibn Al-Haitham Journal For Pure And Applied Science | ||
| Article 1, Volume 27, Issue 2, August 2014, Pages 251-259 | ||
| Author | ||
| Muna M.Salih | ||
| Abstract | ||
| It is frequently asserted that an advantage of a binary search tree implementation of a set over linked list implementation is that for reasonably well balanced binary search trees the average search time (to discover whether or not a particular element is present in the set) is O(logN) to the base 2 where N is the number of element in the set(the size of the tree). This paper presents an experiment for measuring and comparing the obtained binary search tree time with the expected time(theoretical), this experiment proved the correctness of the hypothesis, the experiment is carried out using a program in turbo Pascal with recursion tech-nique implementation and astatistical method to prove the above hypothesis. Search time is estimated by the number of comparisons needed. | ||
| Keywords | ||
| time complexity; Binary Search Tree; Big O Notation; Recursive Method; Chi square; Chi; square | ||
|
Statistics Article View: 170 PDF Download: 42 |
||