title: O(N log N) Complexity - Similar to linear?
body: <p>So I think I'm going to get buried for asking such a trivial question but I'm a little confused about something.</p>
  
  <p>I have implemented quicksort in Java and C and I was doing some basic comparissons. The graph came out as two straight lines, with the C being 4ms faster than the Java counterpart over 100,000 random integers.</p>
  
  <p><img src="https://lh4.ggpht.com/_EW60jqE5_B0/SiwLQa3-rYI/AAAAAAAAAEA/o0-NsWLr1xc/s800/Quicksort.png" alt="Results"></p>
  
  <p>The code for my tests can be found here;</p>
  
  <p><a href="http://code.google.com/p/android-benchmarks/source/browse/#svn/trunk" rel="noreferrer">android-benchmarks</a></p>
  
  <p>I wasn't sure what an (n log n) line would look like but I didn't think it would be straight. I just wanted to check that this is the expected result and that I shouldn't try to find an error in my code.</p>
  
  <p>I stuck the formula into excel and for base 10 it seems to be a straight line with a kink at the start. Is this because the difference between log(n) and log(n+1) increases linearly?</p>
  
  <p>Thanks,</p>
  
  <p>Gav</p>