• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic