Unit 20: Efficiency
Learning Objectives
After completing this unit, students should:
 be aware that efficiency translates to less (and hopefully minimal) computation and space being used by a program
 Understand that increasing efficiency typically requires that there are no redundancies and no duplication (i.e., not repeat work already done)
 understand that when analyzing efficiency, we wish to bound the computation required and thus look at the worstcase scenario
 understand that BigO bounds capture the highest order of growth for some algorithm/code
 be able to determine the BigO bounds for most code used in CS1010
 be able to compare the efficiency between two algorithms using BigO analysis
No Redundant Work
We have been asking you to write efficient code, but we have not been very formal about quantifying what is efficiency. In this unit, we will recap the various good habits to write efficient code, and introduces the notion of time complexity of a code, using the BigO notation.
Writing efficient code means that we should not write code that runs unnecessarily. Let's consider the following two versions of the is_prime
function.
1 2 3 4 5 6 7 8 9 10 

1 2 3 4 5 6 7 8 9 

Both versions are correct  they produce true
when the input n
is prime, and false
otherwise. But they take a vastly different amount of time to run. On my machine, the slower version of is_prime
took ~100s, while the fast one runs ~3ms when invoked with is_prime(10000000001)
. The time taken is a fiveorder of magnitude difference!
The second version of is_prime
is faster as it follows the following mantra:
"No redundant work"
We came across this when we discussed shortcircuiting earlier  we want to order our logical expression so that we don't do extra, unnecessary, work.
Here, we improve the efficiency of is_prime
by (i) returning false
as soon as we found "proof" that the input is not a prime, and (ii) not checking for a divisor that is redundant.
WorstCase Performance
The two techniques we employed above behave slightly differently. For (i), we opportunistically stop our computation once we know the answer when the input is not a prime. However, in the worst case, when the input is a prime, we still have to check through all \(n2\) divisors, from 2 up to \(n1\), before we can conclude that the input is a prime. Thus, for (i), we make our program faster for certain inputs but in the worst case, we are not able to speed up the program.
The second technique is more interesting and more fruitful. With a little math, we can show that we only need to check for the divisor up to \(\sqrt{n}\). Here, we are improving the worst case performance of is_prime
, so whether the input is prime or not, we always have a speedup.
How much is the speedup in the worst case? In the input above, with the original slow code, in the worst case, I need to check through ~10,000,000,001 divisors. With the faster version, I only need to check ~\(\sqrt{10,000,000,001}\) = ~10,000 divisors. That's where the five orders of magnitude speedup come from!
No Duplication
The second principle to improving the efficiency of the program is "No duplication"  we should not repeat work that has been done before.
Let's look at the example from earlier this semester, where you are asked to compute the range of a list. Recall that the range of a list is the absolute difference between the largest element and the smallest element. We use this problem to motivate the use of function, where we denote \(range(L, k) = max(L, k)  min(L, k)\). If we are to implement this solution in C, however, we would end up scanning through the list twice: first to find the max, then to find the min.
But we could easily just go through the list once, using callbyreference to output both the max and the min if we are willing to forgo the notion of pure functions and functionasablackbox.
The performance improvement for not scanning through a list twice is modest at most. Let's look at another example:
1 2 3 4 5 6 7 8 9 

In this version, the loop checks for i <= sqrt(n)
, the terminating condition, every single loop. But, note that n
does not change as we loop, and so sqrt(n)
does not change as well. The code, however, calculates sqrt(n)
over and over again. It is doing duplicated work, recomputing the square root of n
, for nothing. A better code would compute sqrt(n)
once, store it in a variable, and then just read from that variable.
1 2 3 4 5 6 7 8 9 10 

Let's look at another example where, by not repeating ourselves, we can gain significant performance improvement.
Finding Fibonacci Numbers
Recall from your Exercise 4, the Fibonacci sequence of numbers are numbers formed by adding the previous two numbers to form the next numbers. In other words, the \(i\)th Fibonacci number is computed as the sum of the previous two Fibonacci numbers, the \((i2)\)th, and the \((i1)\)th.
Here is one way we can find the Fibonacci numbers with a loop:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

To find the \(n\)th Fibonacci number, we take \(n\) steps in a loop.
Now, let's see the following elegant recursive solution:
1 2 3 4 5 6 7 

This solution is short and follows directly from the definition of Fibonacci numbers. Running this, however, reveals something very disturbing. Let's say we call fib(n)
. This invocation in turns calls fib(n1)
and fib(n2)
. fib(n1)
then calls fib(n2)
and fib(n3)
. So, fib(n2)
will be called twice  so we are repeating ourselves, violating the no duplication principles. We will invoke fib()
many times.
BigO Notation
How do we characterize the number of times fib()
is called? To answer this, we will introduce to you the BigO notation.
The BigO function is a mathematical function that computer scientists use to characterize the time and space efficiency of an algorithm. In CS1010, we will not go into the formal definition of the notation but will introduce BigO using the intuition that it is the "rate of growth" of a function.
Formal definition
For those mathematically inclined students who can't wait until CS2040C or CS3230 for a formal definition, here it is:
Given two functions \(f\) and \(g\), we say that \(f(x) = O(g(x))\) if the exists a position real number \(c\) and a real number \(x_0\) such that
To motivate BigO, let's consider how we can count the number of "steps" taken by an algorithm. Let's consider this again:
1 2 3 4 5 

If we consider each of the fundamental operations: comparison, addition, and assignment, as a step, then we can see that, in each loop, there is one comparison (i != n
), two additions (i + 1
, third = first + second
), four assignments. So we have seven operations per loop, with a total of \(n1\) loops. So we have \(7n  7\) operations. In addition, we also need to count for the assignment i = 2
and the additional comparison before we exit the loop (i != n
). So, in total, we have \(7n  5\) operations.
As you can see, such detailed counting of the steps is tedious, and in fact, not very meaningful. For instance, we did not account for reading values from the memory and writing of values into the memory, the performance of which becomes dependent on the architecture underneath.
To free us from such lowlevel accounting of the number of steps, let's focus on the big picture. No matter how we count the number of steps, in the end, it is a linear function of \(n\). In order words, the number of steps taken by the algorithm to compute Fibonacci in a loop grows linearly with \(n\). Using the BigO notation, we say that it takes \(O(n)\) steps.
Given a mathematical function with multiple terms, the BigO of this function is obtained by dropping any multiplicative constants and all terms, except for the one with the highest rate of growth. For instance, \(O(\frac{n^4}{10} + 10000n^2  n) = O(n^4)\).
Due to this focus on the term with the highest rate of growth, and not bothering about other terms or multiplicative constants, it becomes very convenient for us to express the time efficiency of an algorithm with \(O()\)  we no longer need to count the steps precisely but just focus on the number of times it takes to run the algorithm in terms of \(n\).
Take the example of is_prime
. The slow algorithm takes \(O(n)\), the fast algorithm takes \(O(\sqrt{n})\).
Take another example: to find the range of a list, both algorithms, regardless of whether we are taking two passes or one pass, take \(O(n)\) time.
Comparing Rate of Growth
Given two functions \(f(n)\) and \(g(n)\), how do we determine which one has a higher rate of growth? We say that \(f(n)\) grows faster than \(g(n)\) if we can find a \(n_0\), such that \(f(n) > cg(n)\) for all \(n \ge n_0\) and for some constant \(c\).
For instance, which one grows faster? \(f(n) = n^n\) or \(g(n) = 2^n\)? Pick \(n = 1\), we have \(f(1) < g(1)\)^{1}. Pick \(n = 2\), we have \(f(2)\) equals \(g(2)\). Pick \(n = 3\), we have \(f(3) > g(3)\) now, and we can see that for any \(n > 3\), \(n^n > 2^n\), so we can conclude that \(f(n)\) grows faster than \(g(n)\).
Running Time or Time Complexity of an Algorithm
Using the bigO notation, we can quantify how many steps an algorithm takes to run. This measurement is called the running time or the time complexity of the algorithm.
In CS1010, when we express the running time, we are interested in the worstcase performance, or worstcase running time. Computer scientists also find measuring the average running time useful in certain scenarios. You will learn about analyzing the average running time in CS3230.
There are a couple of things to note when expressing the running of an algorithm in bigO notation:
 We should express it in its simplest form  without multiplicative constants, and dropping all lower terms.
 Since we are specifying the worstcase performance, we are measuring an upper bound on the running time. We should express an upper bound that is as tight as possible.
Example 1: Finding the Maximum
Now, consider the algorithm to find the maximum elements from a list:
1 2 3 4 5 6 7 8 9 10 11 12 

The algorithm scans through the elements in the list onebyone. The number of steps taken is thus \(O(n)\). Note that the number of times we update max_so_far
and max_index
does not matter, since it incurs an additional constant number of steps per element.
Example 2: Rectangle
Now, consider the code below that draw a rectangle:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 

The function draw_line
has a loop that loops \(m2\) times. There is a constant amount of work done before and after the loop (independent of \(m\)). Thus, this function takes \(O(m)\) time.
Now consider draw_rectangle
and focus on the for
loop. The code has a loop that iterates \(n2\) times. For each loop, it calls draw_line
, which takes \(O(m)\). Thus, the total time taken by the for loop is \(O(m \times (n2)) = O(m \times n) = O(mn)\). The function draw_rectangle
also calls draw_line
twice outside the loop. The total running time is \(O(m + mn + m)\), which is still \(O(mn)\).
Note that if we execute the following two lines sequentially,
1 2 

We will incur a running time of \(O(m + n)\) instead.
Example 3: Recursive Max
Consider the divide and concur version of find_max
1 2 3 4 5 6 7 8 9 10 11 12 

What is its running time? Answering this question is trickier since this is a recursive function. But, we can use the same "wishful thinking" approach we used when writing this code to analyze its running time.
Let \(T(n)\) is the running time of find_max
when given the list with \(n\) elements (i.e., end  start
is \(n\)). We can express \(T(n)\) recursively  since we break the list into two halves and recur, we can write \(T(n) = 2T(n/2) + 1\) for \(n > 1\), with the base case \(T(1) = O(1)\).
Note that \(O(1)\) is also known as constant running time^{1}.
The equation for \(T(n)\) above is known as a recurrence relation. There are standard techniques to solve it (search for Master Theorem on the web), but we won't go into them in CS1010. We will solve it from the first principle, by expanding the equation and observing the pattern.
Expanding \(T(n)\), we get
To reach the base case, \(n2^{i} = 1\), so \(2^i = n\) and \(2^{i1} = n/2\). We have
This term \(n/2 + ... + 2 + 1\) a geometric series with a coefficient of 1 and a common ratio of 2. It sums to less than \(n\). We can thus conclude that \(T(n) = O(n)\).
Example 4: Fibonacci
Let's get back to the recursive Fibonacci number example. What is the running time of fib
?
1 2 3 4 5 6 7 

Let \(T(n)\) is the running time of fib(n)
. Since fib(n)
calls fib(n1)
and fib(n2)
,
we can write \(T(n) = T(n1) + T(n2) + 1\). Just like the recursive function there is a base case: \(T(n) = O(1)\) if \(n \le 2\).
We know that \(T(n1) > T(n2)\). So,
therefore,
So
Since we can drop the additive constant in BigO notation, we have \(T(n) = O(2^n)\).
The original analysis above contains a bug that that states \(2^{n2} + ... + 4 + 2 + 1 = O(n)\). This is incorrect and has been fixed above.
This explains why the recursive solution to Fibonacci is so much slower than the iterative version, which is \(O(n)\)  one grows exponentially while the other linearly in terms of \(n\).
Example 5: Collatz
Not every program has a running time that is easy to analyze. For instance, take collatz
1 2 3 4 5 6 7 8 9 

Recall that this program is based on the Collatz conjecture, which has not been proven. So we cannot say that the loop above will always terminate after a given number of steps. The running time for the code above remains unknown.
Space Efficiency
We have focused mostly on efficiency in terms of time in this unit. Note that the notion of efficiency extends to space (memory usage) as well. BigO notation can be used to quantify how much space is used as well.
Problem Set 20
Problem 20.1
Order the following functions in the increasing order of rate of growth:
 \(n!\),
 \(2^n\),
 \(\log_{10} n\),
 \(\ln n\),
 \(n^4\),
 \(n\ln n\),
 \(n\),
 \(n^2\),
 \(e^n\),
 \(\sqrt{n}\)
Problem 20.2
What is the BigO running time of the following code, in terms of \(n\)?
a)
1 2 3 4 5 

b)
1 2 3 4 5 

c)
1 2 3 4 5 

d)
1 2 3 4 5 6 7 

Problem 20.3
a) Express the running time of the following function as a recurrence relation:
1 2 3 4 5 6 

What is its running time?
b) Express the running time of the following function as a recurrence relation:
1 2 3 4 5 6 7 8 9 

What is its running time?