Computer Science Programming Basics in Ruby

7.2 Complexity Analysis

To evaluate an algorithm, a common approach is to analyze its complexity. That is, we essentially count the number of steps involved in executing the algorithm.

An intuitive explanation of complexity analysis is the following. We caution you that our explanation is clearly an oversimplification, but it suffices for our purposes. Given a certain input size, assuming that to process a single element takes one unit of time, how many units of time are involved in processing n elements of input? This is essentially what complexity analysis attempts to answer. As can be seen, it is unnecessary to determine exactly the computer time involved in each step; instead, we simply determine the number of logical steps that occur in a given algorithm. In reality, we can have families of steps (say, one family is addition and subtraction, the other multiplication and division). We then count how many steps of each family are required.

A simple example will be to evaluate the complexity of computing a ²+ab+b ² for a large number, say, n, of pairs of a and b. Computing directly, we should have 3n multiplications and 2n additions. However, we can compute the same expression using (a + b)² – ab, which can be done in 2n multiplications and 2n additions (note that we consider addition and subtraction to be in the same family of steps). Thus, the second expression is better than the original. For very large values of n, this may make a significant difference in computation time. ...