Algorithms of algorithms
Suppose that N equals 1 million. Approximately how much faster is an algorithm that performs NlgN operations versus one that performs N2 operations? Recall that lg is the base-2 logarithm function.
N2/(NlgN)=N/lgN=1,000,000/lg(1,000,000). Since 220 is approximately 1 million, we obtain approximately 50,000.