• Post Reply Bookmark Topic Watch Topic
  • New Topic

TreeMap with incredibly fast access speed. But the question is why?  RSS feed

 
Jackie Luk
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I heard that TreeMaps usually take an access time of O(log(n))
In my case, I've got 600000 elements in the container, it should take around 5.77 secs to find the element
My case took just around 2000 nano secs, which is incredibly fast.
Could anyone explain why this behavior is exhibited? The interface is a SortedMap
Thanks
Jack
 
Paul Clapham
Sheriff
Posts: 22521
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
O(log n) means that if n is the size of the map, then the time to find an entry in the map is less than some multiple of log n, if n is large enough. Of course that multiple depends on several things but you have assumed it to be 1. You might want to have a look at how the big-O notation is defined.
 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jackie Luk wrote:
In my case, I've got 600000 elements in the container, it should take around 5.77 secs to find the element


Big O notation doesn't assign units to the numbers. So, you can't just take the log of a number (of elements) and get the run time (in seconds). Big O is used to determine how an algorithm scales, and even then, it is assuming that the number of elements are approaching infinity.

Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!