 <p>A couple of comments regarding the OP's analysis:</p> <p>I'm assuming you have already constructed your treemaps/sets and are just extracting elements from the finished (preprocessed) in-memory representation. </p> <p>Let's say <em>n</em> is the number of genres. Let's say <em>m</em> is the max number of games per genre.</p> <p>The complexity of getting the right 'genre map' is <code>O(lg n)</code> (a single <code>get</code> for the supertree). The complexity of iterating over the games in that genre depends on how you do it:</p> <pre><code> for (GameRef g : submap.keySet()) { // do something with supermap.get(g) } </code></pre> <p>This code yields <code>O(m)</code> 'get' operations of <code>O(lg m)</code> complexity each, so that's <code>O(m lg(m))</code>.</p> <p>If you do this:</p> <pre><code>for (Map.Entry e : submap.entrySet()) { // do something with e.getValue() } </code></pre> <p>then the complexity is <code>O(m)</code> loop iterations with constant <code>(O(1))</code> time access to the value.</p> <p>Using the second map iteration method, your total complexity is <code>O(lg(n) + m)</code></p>