note
salva
The maths you are doing here are plain wrong!
<p>O expressions only show how an algorithm performance scales depending on the size of the data. They can't be manipulated as regular math expressions, and so <b><c>O(NlogN) / O(N) != logN</c></b> .
<p>Undoing the tipical simplifications performed to get to the O expression, we can obtain a valid expression for the number of operations required by an algorithm. For instance, for an <c>O(NlogN)</c> algorithm as perl built-in sort, the number of operations should be something like <c>A*NlogN + B*N + C</c> (where <c>A</c>, <c>B</c> and <c>C</c> are unknown constants).
<p>For an <c>O(N)</c> algorithm the number of operations is usually <c>B'*N + C'</c>. But when sorting using the ST the cost of the algorithm is still <c>O(NlogN)</c>, you can not ignore the sort step, even if it is implemented in fast C. So the real number of operations is <c>A'*NlogN + B'*N + C'</c>, though <c>A'</c> is much smaller than <c>A</c>.
<p>Considering all this, the resulting relative performance between both algorithms is <c>(A*NlogN + B*N + C)/(A'NlogN + B'*N + C)</c>
<p>It's very different from the <c>logN</c> value you were using and that's why the benchmark results don't mach your expectations.
393128
393128