Algorithm Complexity: Difference between revisions
Line 7: | Line 7: | ||
Algorithm analysis aims at determining the amount of resources consumed by an algorithm while solving a [[Data Structures and Algorithms#Computational_Problem|computational problem]]. In most cases the resource being consumed is time. An analysis can also refer to memory, network bandwidth, etc. | Algorithm analysis aims at determining the amount of resources consumed by an algorithm while solving a [[Data Structures and Algorithms#Computational_Problem|computational problem]]. In most cases the resource being consumed is time. An analysis can also refer to memory, network bandwidth, etc. | ||
<span id='Random_Access_Machine'></span>An algorithm is analyzed in the context of a '''random-access machine'''. '''memory hierarchy'''. | <span id='Random_Access_Machine'></span>An algorithm is usually analyzed in the context of a '''random-access machine'''. '''memory hierarchy'''. | ||
<font color=darkgray> | <font color=darkgray> |
Revision as of 18:58, 6 August 2018
Internal
Overview
Algorithm analysis aims at determining the amount of resources consumed by an algorithm while solving a computational problem. In most cases the resource being consumed is time. An analysis can also refer to memory, network bandwidth, etc.
An algorithm is usually analyzed in the context of a random-access machine. memory hierarchy.
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.
Best-case running time.
Worst-case running time.
Average-case running time.
Expected running time.
Analysis of Insertion Sort
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".