Algorithm Complexity
Jump to navigation
Jump to search
Internal
Overview
Comparing running time for two algorithms of which one is c1n2 and the other is c2 n lg n, even if c2 ≥ c1, no matter how much smaller c1 is than c2, there will always be a crossover point beyond which the c2n lg n algorithm is faster.
Recurrence
The running time of recursive algorithms can be analyzed using recurrences.
A method of analyzing running time of recursive algorithms is the "master theorem".