Algorithm Complexity: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
<font color=darkgray>Comparing running time for two algorithms of which one is c<sub>1</sub>n<sup>2</sup> and the other is c<sub>2</sub>n lg n, even if c<sub>2</sub> ≥ c<sub>1</sub>, no matter how much smaller c<sub>1</sub> is than c<sub>2</sub>, there will always be a crossover point beyond which the c<sub>2</sub>n lg n algorithm is faster. | <font color=darkgray>Comparing running time for two algorithms of which one is c<sub>1</sub>n<sup>2</sup> and the other is c<sub>2</sub> n lg n, even if c<sub>2</sub> ≥ c<sub>1</sub>, no matter how much smaller c<sub>1</sub> is than c<sub>2</sub>, there will always be a crossover point beyond which the c<sub>2</sub>n lg n algorithm is faster. | ||
</font> | </font> | ||
Revision as of 03:36, 5 August 2018
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".