> Is it better to quick-sort one array with 100K elements or quick-sort 3333 30-element subarrays?
> A bit of mathematics can guide us (100000log100000 is 3 times larger than 3333×30log30)
You have to be careful doing this kind of analysis. Big-O is explicitly about what happens for large values of N. It is traditional to leave off smaller factors, because they don't matter at the limit of N going to infinity. There is implicitly a constant coefficient on each component, and that might matter more at small N.
So e.g. I've seen cases that were O(N^2 + N), and which of course you'd traditionally write as O(N^2), but where the O(N) factor mattered more at small values of N because of constant factors. Depending on whether you cared more about small or large values of N, would guide whether you'd actually want to go after the O(N^2) factor or not. If you just blindly went for the larger factor, you could waste a lot of time and not actually accomplish anything.
> A bit of mathematics can guide us (100000log100000 is 3 times larger than 3333×30log30)
You have to be careful doing this kind of analysis. Big-O is explicitly about what happens for large values of N. It is traditional to leave off smaller factors, because they don't matter at the limit of N going to infinity. There is implicitly a constant coefficient on each component, and that might matter more at small N.
So e.g. I've seen cases that were O(N^2 + N), and which of course you'd traditionally write as O(N^2), but where the O(N) factor mattered more at small values of N because of constant factors. Depending on whether you cared more about small or large values of N, would guide whether you'd actually want to go after the O(N^2) factor or not. If you just blindly went for the larger factor, you could waste a lot of time and not actually accomplish anything.