Algorithm Complexity

Internal

• Data Structures and Algorithms

Overview

Describe the RAM model that is used for analysis. Instruction set. Memory hierarchy.

Comparing running time for two algorithms of which one is c₁n² and the other is c₂ n lg n, even if c₂ ≥ c₁, no matter how much smaller c₁ is than c₂, there will always be a crossover point beyond which the c₂n lg n algorithm is faster.

Best case running time.

Worst case running time.

Average case running time.

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".

TODO

• https://en.wikipedia.org/wiki/Big_O_notation
• http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html