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, or predicting, the amount of resources consumed by an algorithm while solving a computational problem. In most cases the resource being consumed is running time, or computational time. An analysis can also refer to memory, network bandwidth, etc.

Random-Access Machine (RAM)

An algorithm is usually analyzed in the context of a random-access machine (RAM), which is a theoretical model for the computing resources typically used by algorithms and their costs. A random-access machine has only one processor. In this model, instructions are executed one after another, with no concurrent operations, though extensions of the model exists when we need to analyze multithreaded algorithms. Algorithms are implemented as computer programs for such a machine. The random-access machine mimics how real computers are designed, so it has instructions commonly found in real computers: arithmetic (add, subtract, multiply, divide, remainder, floor, ceiling), data movement (load, store, copy) and control (conditional branch, subroutine call and return). It is important to emphasize that each instruction takes a constant amount of time - this assumption is essential in algorithm analysis. In accordance with how real computers are implemented, such operations as multiplication with 2^k are also considered constant-time, because they are implemented by shifting left a number representation for k times, as long as k is no more than the number of bits in a computer word.

The data types in the RAM model are integer and floating point. The model assumes a limit on the size of each word of data (if the word size could grow arbitrarily, we could store large amounts of data in one word and operate on it in constant time, which is an unrealistic scenario).

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