9.1. Analysis of Algorithms

Analysis of algorithms

---

Algorithm analysis is concerned with determining how much of a resource, such as time or memory, an algorithm uses as a function of some characteristic of the input to the algorithm, usually the size of the input.

It is common practice to use variable n for the number of characters that it takes to write down the input to an algorithm. Then the time or memory is given as a function of n. For example, a particular algorithm might take time cn² for some constant c.

Big-O notation

---

Usually it is not worth determining the exact cost of running an algorithm. An approximation is all you need. In fact, we usually want to know how the cost depends on n, not what the exact cost is, and it is enough to know that the cost is proportional to some function of n. For expressing that, we use O, Ω and Θ notation.

Let f(n) and g(n) be two functions that take an integer n and yield an integer or real number. f(n and g(n) are mathematical functions, not C++ functions.

Definition. Say that f(n) is O(g(n)) if there are constants c and n₀ so that, for all n ≥ n₀, f(n) ≤ cg(n). That is, for all sufficiently large values of n, f(n) ≤ cg(n).

Definition. Say that f(n) is Ω(g(n)) if there are constants c and n₀ so that, for all n ≥ n₀, f(n) ≥ cg(n).

Definition. Say that f(n) is Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n)).

For example,

• 5n² is O(n²). (Choose c = 5.)
• 3n² + 2n + 10 is O(n²). (Choose n₀ = 10 and c = 5. For all n ≥ 10, 3n² + 2n + 10 ≤ 5n².)
• 2n is O(n²). (Choose n₀ = 2 and c = 1.)
• 5n² is Ω(n²). (Choose c = 1. Certainly, 5n² > n².) Since 5n² is Ω(n²) and 5n² is O(n²), 5n² is Θ(n²).
• 3n² + 2n + 10 is Ω(n²). (What values of n₀ and c will work?) 3n² + 2n + 10 is also O(n²) 3n² + 2n + 10 is Θ(n²).
• 2n is not Ω(n²). function g(n) = n² grows much faster than f(n) = n.

Logarithms

---

x = log₂(y) is defined to be the solution for x to equation y = 2^x. For example, since 2³ = 8, log₂(8) = 3. Here are a few logarithms.

One way to compute an approximate logarithm of an integer x is to start with x and then perform steps where, at each step, you take half of the result of the previous step. But if you get a result that is not an integer, then round down. Stop when you reach 1. Then count the number of halving steps that you did. If you did h halving steps, then h is the largest integer that is ≤ log₂(x). For example,

  1000
   500
   250
   125
    62
    31
    15
     7
     3
     1

Comparisons of common functions

---

Here is a comparison of some common functions of n in terms of how fast they grow as n gets large. The list is in order from slowly growing functions to rapidly growing functions.