We have established that accessing a memory location or storing a value in a memory location is a O(1), or constant time, operation. The same goes for accessing an element of a list or storing a value in a list. The size of the list does not change the time needed to access or store an element and there is a fixed upper bound for the amount of time needed to access or store a value in memory or in a list.

With this knowledge, let's look at the drawing program again and specifically at the piece of code that appends graphics commands to the PyList. This code is used a lot in the program. Every time a new graphics command is created, it is appended to the sequence. When the user is doing some free-hand drawing, hundreds of graphics commands are getting appended every minute or so. Since free-hand drawing is somewhat compute intensive, we want this code to be as efficient as possible.

2.5.1 Inefficient Append

1 class PyList:

2 def init (self):

3 self.items = []

4

5 # The append method is used to add commands to the sequence.

6 def append(self,item):

7 self.items = self.items + [item]

8

9 ...

The code in Sect. 2.5.1 appends a new item to the list as follows:

1. The item is made into a list by putting [and] around it. We should be careful about how we say this. The item itself is not changed. A new list is constructed from the item.

2. The two lists are concatenated together using the + operator. The + operator is an accessor method that does not change either original list. The concatenation creates a new list from the elements in the two lists.

3. The assignment of self.items to this new list updates the PyList object so it now refers to the new list.

The question we want to ask is, how does this append method perform as the size of the PyList grows? Let's consider the first time that the append method is called. How many elements are in the list that is referenced by self.items? Zero, right? And there is always one element in [item]. So the append method must access one element of a list to form the new list, which also has one element in it.

What happens the second time the append method is called? This time, there is one element in the list referenced by self.items and again one element in [item]. Now, two elements must be accessed to form the new list. The next time append is called three elements must be accessed to form the new list. Of course, this pattern continues for each new element that is appended to the PyList. When the nth element is appended to the sequence there will have to be n elements copied to form the new list. Overall, how many elements must be accessed to append n elements?

2.6 A Proof by Induction

We have already established that accessing each element of a list takes a constant amount of time. So, if we want to calculate the amount of time it takes to append n elements to the PyList we would have to add up all the list accesses and multiply by the amount of time it takes to access a list element plus the time it takes to store a list element. To count the total number of access and store operations we must start with the number of access and store operations for copying the list the first time an element is appended. That's one element copied. The second append requires two copy operations. The third append requires three copy operations. So, we have the following number of list elements being copied.

In mathematics we can express this sum with a summation symbol (i.e. Y). This is

the mathematical way of expressing the sum of the first n integers. But, what is this equal to? It turns out with a little work, we can find that the following is true.

We can prove this is true using a proof technique from Mathematics called mathematical induction. There are a couple of variations of mathematical induction. We'll use what is called weak induction to prove this. When proving something using induction you are really constructing a meta-proof. A meta-proof is a set of steps that you can repeat over and over again to find your desired result. The power of induction is that once we have constructed the meta-proof, we have proved that the result is true for all possible values of n.

We want to prove that the formula given above is valid for all n. To do this we first show it is true for a simple value of n. In our case we'll pick 1 as our value of

n. In that case we have the following.

This is surely true. This step is called the base case of the inductive proof. Every

proof by induction must have a base case and it is usually trivial.

The next step is to create the meta-proof. This meta-proof is called the inductive case. When forming the inductive case we get to assume that the formula holds for all values, m, where m is less than n. This is called strong induction. In weak induction we get to assume that the formula is valid for n −1 and we want to show that it is valid for

n. We'll use weak induction in this problem to finish our proof. Again, this step helps

us form a set of steps that we can apply over and over again to get from our base case to whatever value of n we need to find. To begin we will make note of the following.

This is true by the definition of summation. But now we have a sum that goes to n − 1 and weak induction says that we know the equation is valid for n − 1 . This is called the inductive hypothesis. Since it holds for n − 1 we know the following is true. We get this by substituting n − 1 everyplace that we see an n in the original formula.

Now we can use this fact in proving the equality of our original formula. Here we go!

If you look at the left side and all the way over at the right side of this formula you can see the two things that we set out to prove were equal are indeed equal. This concludes our proof by induction. The meta-proof is in the formula above. It is a template that we could use to prove that the equality holds for n = 2. To prove the

equality holds for n = 2 we needed to use the fact that the equality holds for n = 1.

This was our base case. Once we have proved that it holds for n = 2 we could use that same formula to prove that the equality holds for n = 3. Mathematical induction doesn't require us to go through all the steps. As long as we've created this meta-proof

we have proved that the equality holds for all n. That's the power of induction.

Found a mistake? Please highlight the word and press Shift + Enter