Chapter 2: Basics of Algorithm Analysis

Several factors are key in the design of algorithms, including understanding the discrete nature of many problems as well as addressing the efficiency and space of an algorithm. The text gives one definition of efficiency: “An algorithm is efficient if, when implemented, it runs quickly on real input instances.” Unfortunately, this definition fails to consider where and how well the algorithm is implemented.

To be more specific, we can argue that an algorithm is efficient if it, at the bare minimum, performs in the worst case better than would a brute-force search. To narrow the definition even further, we could classify an 'efficient algorithm' as one with a polynomial running time, meaning its running time is bounded by cN^d where c and d are constants > 0 and every input instance is size N.

For the purposes of simplicity and clarity, classifying running times should be done in terms of constant factors; for example instead of calculating a run time as an² + bn + c, we would consider this run time to be simply n². Assume T(n) is the worst-case run time for an algorithm with n referring to the size of the input. Let f(n) refer to a function. T is asymptotically upper-bounded and T(n) is order f(n) if:

• there exists a constant c > 0
• there exists and a constant n₀ ≥ 0 such that

all n ≥ n₀, and

• T(n) ≤ c.