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> | ||
Describe the RAM model that is used for analysis. Instruction set. Memory hierarchy. | |||
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 17:59, 6 August 2018
Internal
Overview
Describe the RAM model that is used for analysis. Instruction set. Memory hierarchy.
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".