計算量オーダーを減らせば必ず高速化するわけではない

プログラムの処理速度を向上させたい場合、まず注目すべき点がアルゴリズムの計算量だと思います。

計算量オーダーを$O(n^2)$から$O(n\log{n})$に減らせれば大幅な高速化が期待できる、と思うのが普通ですが実際にやってみると必ずしも高速化しない場合があります。

解説

ご存知の通り、あるアルゴリズムの計算量は一般的にO記法（ランダウの記号）を用いて示されます。
（注：必要なメモリを表す空間計算量も同様にO記法を用いますが、ここでは時間計算量について扱います）
O記法は入力の大きさ$n$に対する時間の増加の仕方を表すものですので、実際に何秒かかるかということを示すものではありません。

計算量$O(n^2)$のアルゴリズムは$n$が2倍になったとき、計算時間は4倍になると分かりますが、大事なのは実際にそれが何秒かかるかということです。
それを知るためにはどこか任意の$n$、例えば$n=1$でもいいですし、実際に入力されると想定される範囲の$n$を入力してみて時間を測定する必要があります。
（恐らく多くの場合、$n=1$では時間が短すぎて測定精度が悪いと思うので、実用上の$n$を入力するのが良いと思います）

例えば、以下のようなCのコードは計算量が$O(n^2)$で、$n=1$のとき処理時間は1秒ですから、$n=10$であれば処理時間は100秒であることが予想されます。

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // ここで1秒かかる処理
    }
}

ではすごいアルゴリズムが見つかって、計算量オーダーを$O(n)$に落とせたとします。
その代わりループの中の処理はやや複雑になり、時間がかかるようになりました。

for (int i = 0; i < n; i++) {
    // ここで10秒かかる処理
}

$n$と処理時間をグラフに表すと以下のようになります。
$n<10$においてはこのアルゴリズム変更はむしろ逆効果であることが分かります。

このグラフは、計算時間を以下のように求めています。
$T=n^2$
$T=10n$

O記法では支配的な項のみを記載するため、非支配的な項（例えば$O(n^2)$であれば2乗未満の項があったとしても記載しない）や定数倍については省略されます。
支配的とは「値が大きい場合」の話なので、逆に言えば値が小さい場合には非支配的な項も無視出来ません。

計算量オーダーを落とすために工夫を凝らした複雑なアルゴリズムの場合、この例のように1ループにかかる時間が伸びる場合があります。
凝ったアルゴリズムをがんばって実装したのに、$n$が小さいために効果が無いどころか逆効果だった・・・ということもありえます。

普通は大きい$n$に対してアルゴリズムの改善を実施すると思うので問題になることは多くはないと思いますが「$n$は小さいが時間がかかっているようなループ」に対して「複雑だが計算量を落とせるアルゴリズム」を適用するような場合には注意が必要です。