Algorithm Complexity

External

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

Internal

• Data Structures and Algorithms

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

Expected running time.

Order of growth

Analysis of Insertion Sort

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