Alex Rivera | Logout

What is difference between Array and Binary search tree in efficiency?

Asked 2011-12-27T16:35:57.530
12

I want know what is the best : Array OR Binary search tree in ( insert , delete , find max and min ) and how can I Improve both of them ?

arrays algorithm binary-search-tree processing-efficiency
Edit
Report

1 Answer

18

Performance comparison of Arrays and Binary search trees:

                 Array                     Binary search tree
          Unsorted   Sorted           Average            Worst case
Space      O(n)       O(n)             O(n)               O(n)
Search     O(n)       O(log n) *       O(log n)           O(n)
Max/Min    O(n)       O(1)             O(1) **            O(1) **
Insert     O(1)       O(n)             O(log n)           O(n)
Delete     O(1)       O(n)             O(log n)           O(n)

* assuming binary search

** requires extra pointers to min and max, otherwise it's O(log n)

answered 2011-12-27T17:05:38.733

Your Answer