This week we dove more deeply into the analysis of algorithms. Last week introduced order of growth, and this week expanded on that with asymptotic notation, analysis of non-recursive and recursive algorithms, and the first design technique, brute force.
Asymptotic notation
| Notation | Meaning | Formal condition |
|---|---|---|
| O(g(n)) | Upper bound | t(n) ≤ c·g(n) for all n ≥ n₀ |
| Ω(g(n)) | Lower bound | t(n) ≥ c·g(n) for all n ≥ n₀ |
| Θ(g(n)) | Tight bound | c₁·g(n) ≤ t(n) ≤ c₂·g(n) for all n ≥ n₀ |
The table above is based on the definitions given in section 2.2 of the Levitin’s textbook. Big-O, Big-Omega, and Big-Theta each compare an algorithm’s running time t(n) to a simpler function g(n), such as n or n².
For orders of growth, we only care about large inputs, so each condition has to hold from some starting size n₀ onward.
O(g(n)) is the upper bound: after n₀, t(n) never grows faster than some constant multiple c of g(n).
Ω(g(n)) is the lower bound: after n₀, t(n) always grows at least as fast as a constant multiple of g(n).
Θ(g(n)) is the tight bound: t(n) stays between two constant multiples of g(n), so it is both O(g(n)) and Ω(g(n)) and has the same order of growth.
The constants are what let us ignore details. You can pick any c and n₀ that make the inequality true, so coefficients and lower-order terms don’t change the classification. For example, 2n + 3 is Θ(n) because n ≤ 2n + 3 ≤ 3n for all n ≥ 3.
Analyzing non-recursive algorithms
To analyze a non-recursive algorithm, you count the basic operation, which is usually found in the innermost loop. Once the basic operation is identified, you determine how many times it runs, in terms of n, and simplify to get the order of growth.
For example, if an algorithm’s basic operation is in a nested loop, that runs n times for the outer loop and n times for the inner loop, then the order of growth is Θ(n²)
Analyzing recursive algorithms
A recursive algorithm’s count is written as a recurrence relation plus an initial condition from the base case, which can then be solved by backward substitution.
To solve a recurrence relation, substitute repeatedly until a pattern appears, generalize the pattern in terms of i, and then choose the i that reaches the base case, in order to express the relation in terms of n.
Brute force
Brute force means solving a problem directly from its definition, usually by trying every possibility. It can often be slow, but it’s a good starting point towards a more efficient solution.