title: How can I calculate the Big O complexity of my program?
body: <p>I have a Big O notation question. Say I have a Java program that does the following things:</p>
  
  <ol>
  <li><p>Read an Array of Integers into a <code>HashMap</code> that keeps track of how many occurrences of the Integers exists in the array. [1,2,3,1] would be [1->2, 2->1, 3->1].</p></li>
  <li><p>Then I grab the Keys from the <code>HashMap</code> and place them in an <code>Array</code>:</p>
  
  <pre><code>Set&lt;Integer&gt; keys = dictionary.keySet();
  Integer[] keysToSort = new Integer[keys.size()];
  keys.toArray(keysToSort);
  </code></pre></li>
  <li><p>Sort the <code>keyArray</code> using <code>Arrays.sort</code>.</p></li>
  <li><p>Then iterate through the sorted <code>keyArray</code> grabbing the corresponding value from the <code>HashMap</code>, in order to display or format the results.</p></li>
  </ol>
  
  <p>I think I know the following:</p>
  
  <ul>
  <li>Step 1 is O(n)</li>
  <li>Step 3 is O(n log n) if I'm to believe the Java API</li>
  <li><p>Step 4 is O(n)</p></li>
  <li><p>Step 2: When doing this type of calculation I should know how Java implements the <code>Set</code> class <code>toArray</code> method.  I would assume that it iterates through the <code>HashMap</code> retrieving the <code>Keys</code>.  If that's the case I'll assume its O(n).</p></li>
  </ul>
  
  <p>If sequential operations dictate I add each part then the final calculation would be
  O(n + n·log n + n+n) = O(3n+n·log n).</p>
  
  <p>Skip the constants and you have <strong>O(n+n log n)</strong>. Can this be reduced any further or am I just completely wrong?</p>