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
• Liutauras Vilda
• Tim Cooke
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Devaka Cooray
• Ron McLeod
• paul wheaton
Saloon Keepers:
• Tim Moores
• Piet Souris
• Tim Holloway
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Frits Walraven
• Scott Selikoff

# PriorityQueue

Ranch Hand
Posts: 1491
• Number of slices to send:
Optional 'thank-you' note:

PriorityQueue Implementation note: this implementation provides O(log(n)) time for the insertion methods

What is the meaning of O(log(n)) ?

Sheriff
Posts: 11343
• Number of slices to send:
Optional 'thank-you' note:
See Wikipedia - Big O Notation and An informal introduction to O(N) notation, the latter of which says...

O(N) notation is used to express the worst-case order of growth of an algorithm. That is, how the algorithm's worst-case performance changes as the size of the data set it operates on increases.

...and specifically...

O(log N) and O(N log N) ... generally mean that the algorithm deals with a data set that is iteratively partitioned, like a balanced binary tree... Generally, but not always, log N implies log2N, which means, roughly, the number of times you can partition a set in half, then partition the halves, and so on, while still having non-empty sets.

Bartender
Posts: 4568
9
• 1
• Number of slices to send:
Optional 'thank-you' note:
In this case, it means inserting items into a PriorityQueue that contains n items (where n is large - these scalings are only really relevant for big numbers) scales with log(n). Let's say that you've got a queue with 10,000 entries, and it's taking four seconds to insert items (in the worst case). Then you'd expect a queue with 100,000 entries to take five second to insert items [because log(10000) = 4 and log(100000) = 5].

 So it takes a day for light to pass through this glass? So this was yesterday's tiny ad? the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising