5.4 Evaluating the Python List

On this page...

List Traversal
List Allocation
Appending to a List
Extending a List
Inserting and Removing Items

We defined several abstract data types for storing and using collections of data in the previous chapters. The next logical step is to analyze the operations of the various AD Ts to determine their efficiency. The result of this analysis depends on the efficiency of the Python list since it was the primary data structure used to implement many of the earlier abstract data types.

The implementation details of the list were discussed in Chapter 3. In this section, we use those details and evaluate the efficiency of some of the more common operations. A summary of the worst case run times are shown in Table 5.4.1.

List Operations	Worst Case
`v = list()`	$O (1)$
`v = [ 0 ] * n`	$O (n)$
`len(v)`	$O (1)$
`v[i] = x`	$O (1)$
`v.append(x)`	$O (n)$
`v.insert(x)`	$O (n)$
`v.pop(i)`	$O (n)$
traversal	$O (n)$

Table 5.4.1: Worst case time-complexities for the more common list operations.

List Traversal

A sequence traversal accesses the individual items, one after the other, in order to perform some operation on every item. Python provides the built-in iteration for the list structure, which accesses the items in sequential order starting with the first item. Consider the following code segment, which iterates over and computes the sum of the integer values in a list:

sum = 0

for value in valueList :

  sum = sum + value

To determine the order of complexity for this simple algorithm, we must first look at the internal implementation of the traversal. Iteration over the contiguous elements of a 1-D array, which is used to store the elements of a list, requires a count-controlled loop with an index variable whose value ranges over the indices of the subarray. The list iteration above is equivalent to the following:

sum = 0

for i in range(len(valueList)) :

  sum = sum + valueList[i]

list traversal

worst-case:

O (n)

Assuming the sequence contains $n$ items, it's obvious the loop performs $n$ iterations. Since all of the operations within the loop only require constant time, including the element access operation, a complete list traversal requires $O (n)$ time. Note, this time establishes a minimum required for a complete list traversal. It can actually be higher if any operations performed during each iteration are worse than constant time, unlike this example.

List Allocation

Creating a list, like the creation of any object, is considered an operation whose time-complexity can be analyzed. There are two techniques commonly used to create a list:

temp = list()

valueList = [ 0 ] * n

list allocation

worst-case:

O (n)

The first example creates an empty list, which can be accomplished in constant time. The second creates a list containing $n$ elements, with each element initialized to 0. The actual allocation of the $n$ elements can be done in constant time, but the initialization of the individual elements requires a list traversal. Since there are $n$ elements and a traversal requires linear time, the allocation of a vector with $n$ elements requires $O (n)$ time.

Appending to a List

list append

best-case:

O (1)

worst-case:

O (n)

The append operation adds a new item to the end of the sequence. If the underlying array used to implement the list has available capacity to add the new item, the operation has a best case time of $O (1)$ since it only requires a single element access. In the worst case, there are no available slots and the array has to be expanded using the steps described in Section Vector.

Creating the new larger array and destroying the old array can each be done in $O (1)$ time. To copy the contents of the old array to the new larger array, the items have to be copied element by element, which requires $O (n)$ time. Combining the times from the three steps yields a time of $T (n) = 1 + 1 + n$ and a worst case time of $O (n)$ .

Extending a List

extend list

worst-case:

O (n)

The extend operation adds the entire contents of a source list to the end of the destination list. This operation involves two lists, each of which have their own collection of items that may be of different lengths. To simplify the analysis, however, we can assume both lists contain $n$ items. When the destination list has sufficient capacity to store the new items, the entire contents of the source list can be copied in $O (n)$ time. But if there is not sufficient capacity, the underlying array of the destination list has to be expanded to make room for the new items. This expansion requires $O (n)$ time since there are currently $n$ items in the destination list. After the expansion, the $n$ items in the source list are copied to the expanded array, which also requires $O (n)$ time. Thus, in the worst case the extend operation requires $T (n) = n + n = 2 n$ or $O (n)$ time.

Inserting and Removing Items

Inserting a new item into a list is very similar to appending an item except the new item can be placed anywhere within the list, possibly requiring a shift in elements. An item can be removed from any element within a list, which may also involve shifting elements. Both of these operations require linear time in the worst case, the proof of which is left as an exercise.

5.3 Evaluating Python Code

Chapter 5. Algorithm Analysis

5.5 Amortized Cost