algorithm - O(n log n) vs O(n) -- practical differences in time complexity -

n log n > n -- pseudo-linear relationship. if n=1 billion, log n ~ 30;

so n log n 30 billion, 30 x n, order of n. wondering if time complexity difference between n log n , n significant in real life.

eg: quick select on finding kth element in unsorted array o(n) using quickselect algorithm.

if sort array , find kth element, o(n log n). sort array 1 trillion elements, 60 times slower if quicksort , index it. me sounds not big difference, need opinion of experts here.

the main purpose of big-o notation let estimates ones did in post, , decide if spending effort coding typically more advanced algorithm worth additional cpu cycles going buy code improvement. depending on circumstances, may different answer, when data set relatively small:

• if running on mobile device, , algorithm represents significant portion of execution time, cutting down use of cpu translates extending battery life
• if running in all-or-nothing competitive environment, such high-frequency trading system, micro-optimization may differentiate between making money , losing money
• when profiling shows algorithm in question dominates execution time in server environment, switching faster algorithm may improve performance clients.

another thing big-o notation hides constant multiplication factor. example, quick select has reasonable multiplier, making time savings employing on extremely large data sets worth trouble of implementing it.

another thing need keep in mind space complexity. often, algorithms o(n*log n) time complexity have o(log n) space complexity. may present problem extremely large data sets, example when recursive function runs on system limited stack capacity.