Chapter 2. Algorithm Analysis
We can compare the efficiency of algorithms without implementing them. Our two most important tools are (1) the RAM model of computation and (2) the asymptotic analysis of worst-case complexity.
2.1 The RAM Model of Computation
Machine-independent algorithm design depends upon a hypothetical computer called the Random Access Machine or RAM
- Each simple operation (+, *, –, =, if, call) takes exactly one time step.
- Loops and subroutines are not considered simple operations
- Each memory access takes exactly one time step
Best, Worst, and Average-Case Complexity
Using the RAM model of computation, we can count how many steps our algorithm takes on any given input instance by executing it. However, to understand how good or bad an algorithm is in general, we must know how it works over all instances.
2.2 The Big Oh Notation
The formal definitions associated with the Big Oh notation are as follows:
- f(n) = O(g(n)) means c · g(n) is an upper bound on f (n). Thus there exists some constant c such that f (n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
- f(n) = Ω(g(n)) means c · g(n) is a lower bound on f(n). Thus there exists some constant c such that f(n) is always ≥ c · g(n), for all n ≥ n0.
- f(n) = Θ(g(n)) means c1 · g(n) is an upper bound on f(n) and c2 · g(n) is a lower bound on f(n), for all n ≥ n0. Thus there exist constants c1 and c2 such that f (n) ≤ c1 · g(n) and f (n) ≥ c2 · g(n). This means that g(n) provides a nice, tight bound on f(n).

Notice the n0 in the figure. We choose certain constants (c and n0) in the explanations:
3n² − 100n + 6 = O(n²), because I choose c = 3 and 3n² > 3n² − 100n + 6;
3n² − 100n + 6 = O(n³), because I choose c = 1 and n³ > 3n² − 100n + 6 when n > 3;
3n²−100n+6 !=O(n),because for any c I choose c×n < 3n² when n>c;
Stop and Think: Back to the Definition



2.3 Growth Rates and Dominance Relations

nanosecond (ns)is 10^-9 second, microsecond (μs)is 10^-6 second, millisecond (ms) is (10^-3) second
Dominance Relations
Complexity of algorithms
- Constant f(n) = 1
- Logarithmic f(n) = log n. binary search
- Linear f(n) = n
- Superlinear f(n) = n lg n. quick sort, merge sort
- Quadratic f(n) = n²
- Cubic f(n) = n³. Such functions enumerate through all triples of items in an n-element universe
- Exponential f(n) = c^n. Functions like 2^n arise when enumerating all subsets of n items.
- Factorial f(n) = n!. Functions like n! arise when generating all permutations or orderings of n items.
2.4 Working with the Big Oh
O(f (n)) + O(g(n)) → O(max(f (n), g(n)))
Ω(f (n)) + Ω(g(n)) → Ω(max(f (n), g(n)))
Θ(f (n)) + Θ(g(n)) → Θ(max(f (n), g(n)))
If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)).
2.5 Reasoning About Efficiency
String Pattern Matching
Problem: Substring Pattern Matching
Input: A text string t and a pattern string p.
Output: Does t contain the pattern p as a substring, and if so where?

Time complexity: O(n + m + (n − m)(m + 2)) => O(nm) where n + m is for strlen functions, n-m is for outer loop and m+2 is inner loop plus two other statements.
2.6 Logarithms and Their Applications
Saying b^x = y is equivalent to saying that x = logby. Further, this definition is the same as saying b^(logby) = y.
Logarithms and Trees
A binary tree of height 1 can have up to 2 leaf nodes, while a tree of height two can have up to four leaves. What is the height h of a rooted binary tree with n leaf nodes? Note that the number of leaves doubles every time we increase the height by one. To account for n leaves, n = 2^h which implies that h = log2 n.
Logarithms arise whenever things are repeatedly halved or doubled.
2.7 Properties of Logarithms
As we have seen, stating b^x = y is equivalent to saying that x = logb y. The b term is known as the base of the logarithm. Three bases are of particular importance for mathematical and historical reasons:
- Base b = 2. The binary logarithm, usually denoted lg x, is a base 2 logarithm. We have seen how this base arises whenever repeated halving (i.e., binary search) or doubling (i.e., nodes in trees) occurs. Most algorithmic applications of logarithms imply binary logarithms.
- Base b = e. The natural log, usually denoted lnx, is a base e = 2.71828... logarithm. The inverse of ln x is the exponential function exp(x) = ex on your calculator. Thus, composing these functions gives us
exp(ln x) = x. - Base b = 10. Less common today is the base-10 or common logarithm, usually denoted as log x. This base was employed in slide rules and logarithm books in the days before pocket calculators.
Two implications of these properties of logarithms are important to appreciate from an algorithmic perspective:
- The base of the logarithm has no real impact on the growth rate. We are usually justified in ignoring the base of the logarithm when analyzing algorithms
- Logarithms cut any function down to size. The growth rate of the logarithm of any polynomial function is O(lg n). This follows because
loga nb = b·loga n
2.8 … Omitted
2.9 Advanced Analysis (*)
Limits and Dominance Relations
The dominance relation between functions is a consequence of the theory of lim- its, which you may recall from Calculus. We say that f(n) dominates g(n) if limn→∞ g(n)/f(n) = 0. e.g. f(n) = n³ and g(n) = n².


