Design and Analysis of Algorithms

Effi ciency of Algorithms 401

1. Amdahl’s law named after computer ar-

chitect Gene Amdahl, is used to fi nd the

maximum expected improvement to an

overall system when only part of the system

is improved. The law is concerned with the

speedup achievable from an improvement to

a computation that affects a proportion P of

that computation where the improvement has

a speedup of S.

2. Asymptotic domination the property of a

term in an expression for running time, which

dominates as the problem size increases.

3. Asymptotic time is time taken by an algo-

rithm as the problem size grows bigger and

bigger, tending to infi nity.

4. Big-Oh notation ...