3

If searching a sorted List is O(log2 n) and searching a balanced BST is also O(log2 n), which one should I use assuming the following:

  1. Elements will be received unsorted and then sorted after all the elements are loaded
  2. No elements will be removed

Which should be used and why (Sorted List or Binary Search Tree)?

Thanks.

PhillyNJ
  • 3,859
  • 4
  • 38
  • 64
  • 2
    smells like homework :) (if so, please add the appropriate tag) – Muad'Dib Nov 21 '11 at 00:23
  • point (1) would seem to indicate that a sorted list is appropriate.... – Mitch Wheat Nov 21 '11 at 00:23
  • LOL - not a homework question , but I am studying Data Structures and want to know whats the best approach. I have an upcoming project where I will load about 850,000 elements for searching. – PhillyNJ Nov 21 '11 at 00:30
  • As a side note, it's not necessary to say it's O(log2 n), O(log n) is exactly the same (the difference between log2 n and log n is a constant). – svick Nov 21 '11 at 00:38
  • possible duplicate of [When to use a SortedList over a SortedDictionary?](http://stackoverflow.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue) – nawfal Jun 15 '14 at 08:41

3 Answers3

3

If you sort the data once and then only search, then the asymptotic complexities of both approaches will be the same.

I think sorted list will have much lower actual running time and memory consumption, indexing into an array is extremely fast.

That being said, maybe using a hash table would be better for you. Creating it is O(n) (compared with O(n log n) of the previous approaches) and retrieving one item is O(1) (compared with O(log n)).

svick
  • 236,525
  • 50
  • 385
  • 514
2

Would it be overly difficult to set up both (/all three) and then benchmark them? You could abstract the data structure out of it with a wrapper class and then just change the wrapper class between benchmarks. Of course, I'm assuming that you have infinite time here. :)

Hotchips
  • 621
  • 5
  • 18
1

They will both be O(n log n) to create/sort. All will be O(log n) to retrieve.

In actuality, a sorted binary tree can be represented as a sorted array, as long as it's a complete perfect tree. So they are, in essence, the exact same thing.

DanTheMan
  • 3,277
  • 2
  • 21
  • 40