Remember, that all asymptotic analysis tells us is how the running time varies with the size of the input for a particular algorithm. It doesn't tell us how many seconds it will take for an implementation of the algorithm to complete with a given input size. But we do know that if an O(n^{2</sup)) algorithm takes X seconds to process a set of items, it will take approximately 100 times as long to process 10 times as many items.}

Asymptotic notation eliminates constant factors because they're not really relevant to how the running time grows with the size of input. When you're talking about using an O(n²) algorithm on 1,000,000 items, it's unlikely that your constant factor is going to make much difference; the n^2 term is going to dwarf it.

You can, however, estimate the constant factors. One way is by counting "basic operations" to come up with a rough estimate of how much work is done per iteration. Or, you could run both algorithms with some sample input, count the iterations, and figure out how many microseconds it takes per iteration. Either way, you'll come up with a value that is the constant for that particular algorithm.

So, say you want to compare insertion sort (an O(n²) algorithm with Quick sort (O(n log n)). We know from empirical evidence that insertion sort is faster than Quick sort when n is small (how small is another question). That's why optimized Quick sort implementations switch to insertion sort when the subarray is less than 10 or so items.

Using one of the techniques I described above, you determine the constants for each of the algorithms. Let's call them C_i and C_q. Given that, we can estimate that insertion sort will be faster than Quick sort when (C_i * n2) <(C_q*(n log n)).

Remember, that all asymptotic analysis tells us is how the running time varies with the size of the input for a particular algorithm. It doesn't tell us how many seconds it will take for an implementation of the algorithm to complete with a given input size. But we do know that if an O(n²)) algorithm takes X seconds to process a set of items, it will take approximately 100 times as long to process 10 times as many items.

Asymptotic notation eliminates constant factors because they're not really relevant to how the running time grows with the size of input. When you're talking about using an O(n²) algorithm on 1,000,000 items, it's unlikely that your constant factor is going to make much difference; the n^2 term is going to dwarf it.

You can, however, estimate the constant factors. One way is by counting "basic operations" to come up with a rough estimate of how much work is done per iteration. Or, you could run both algorithms with some sample input, count the iterations, and figure out how many microseconds it takes per iteration. Either way, you'll come up with a value that is the constant for that particular algorithm.

So, say you want to compare insertion sort (an O(n²) algorithm with Quick sort (O(n log n)). We know from empirical evidence that insertion sort is faster than Quick sort when n is small (how small is another question). That's why optimized Quick sort implementations switch to insertion sort when the subarray is less than 10 or so items.

Using one of the techniques I described above, you determine the constants for each of the algorithms. Let's call them C_i and C_q. Given that, we can estimate that insertion sort will be faster than Quick sort when (C_i * n²) < (C_q*(n log n)).

Remember, that all asymptotic analysis tells us is how the running time varies with the size of the input for a particular algorithm. It doesn't say anything about the actual running time.

Now, consider the simple case of insertion sort (O(n^2)) and Quick sort (O(n log n)). We know from empirical evidence that insertion sort is faster than Quick sort when n is small (how small is another question). That's why optimized Quick sort implementations switch to insertion sort when the subarray is less than 10 or so items.

Asymptotic notation eliminates constant factors. If you add the constant factors then Quick sort's running time becomes O(C_q*(n log n)), and Insertion sort's running time is O(C_i*n^2). So in that case, Insertion sort will be faster than Quick sort when C_in² < C_q(n log n).

It should be obvious from looking at the two algorithms that Ci < Cq. The insertion sort is incredibly simple. The algorithm is nothing but comparison and swap, with a little loop overhead thrown in.

So the partition method will be called four times. Each partition step requires a minimum of two swaps in addition to the comparison and swapping of elements, and other overhead. When you add it all up, you see that Quicksort does more work per iteration. When the number of iterations is small, Insertion sort does less total work even though it does more iterations.

You can do a step-by-step analysis to determine the theoretical value of "small," where Insertion sort will be faster than Quicksort. Typically that's done by counting "basic operations," although the definition is somewhat flexible. In this case it's pretty easy: a comparison, assignment, or function call is a "basic operation."

How the theoretical result matches up with the experimentally derived result will depend on the particular computer hardware and also on how expensive comparisons are. If comparisons are very expensive, then you'll want to select the algorithm that does the fewest number of comparisons. But if comparisons are relatively inexpensive (comparing numbers, for example, or even strings provided that they don't have long common prefixes), then the algorithmic overhead is the limiting factor and the simple inefficient algorithm outperforms the complex efficient algorithm.

Remember, that all asymptotic analysis tells us is how the running time varies with the size of the input for a particular algorithm. It doesn't tell us how many seconds it will take for an implementation of the algorithm to complete with a given input size. But we do know that if an O(n^{2</sup)) algorithm takes X seconds to process a set of items, it will take approximately 100 times as long to process 10 times as many items.}

Asymptotic notation eliminates constant factors because they're not really relevant to how the running time grows with the size of input. When you're talking about using an O(n²) algorithm on 1,000,000 items, it's unlikely that your constant factor is going to make much difference; the n^2 term is going to dwarf it.

You can, however, estimate the constant factors. One way is by counting "basic operations" to come up with a rough estimate of how much work is done per iteration. Or, you could run both algorithms with some sample input, count the iterations, and figure out how many microseconds it takes per iteration. Either way, you'll come up with a value that is the constant for that particular algorithm.

So, say you want to compare insertion sort (an O(n²) algorithm with Quick sort (O(n log n)). We know from empirical evidence that insertion sort is faster than Quick sort when n is small (how small is another question). That's why optimized Quick sort implementations switch to insertion sort when the subarray is less than 10 or so items.

Using one of the techniques I described above, you determine the constants for each of the algorithms. Let's call them C_i and C_q. Given that, we can estimate that insertion sort will be faster than Quick sort when (C_i * n2) <(C_q*(n log n)).

It should be obvious from looking at the two algorithms that C_i < C_q. The insertion sort is incredibly simple. The algorithm is nothing but comparison and swap, with a little loop overhead thrown in.

So the partition method will be called four times. Each partition step requires a minimum of two swaps in addition to the comparison and swapping of elements, and other overhead. When you add it all up, you see that Quicksort does more work per iteration. When the number of iterations is small, Insertion sort does less total work even though it does more iterations.