Previous Section
 < Free Open Study > 
Next Section


3.5 Comparison of Unsorted and Sorted List ADT Algorithms

To determine the Big-O notation for the complexity of these functions, we must first determine the size factor. Here we are considering algorithms to manipulate items in a list, so the size factor is the number of items on the list: length.

Many of our algorithms are identical for the Unsorted List ADT and the Sorted List ADT. Let's examine these algorithms first. MakeEmpty (the class constructor) contains one line: length is set to 0. LengthIs and IsFull each contain only one statement: return length and return (length == MAX_ITEMS). As none of these functions depends on the number of items in the list, each has O(1) complexity. ResetList contains one assignment statement and GetNextItem contains two assignment statements. Neither of these functions depends on the number of items in the list, so each has O(1) complexity.

The other functions differ for the two implementations.

Unsorted List ADT

The algorithm for RetrieveItem requires that the list be searched until an item is found or the end of the list is reached. We might find the item in any position in the list, or we might not find it at all. How many places must we examine? At best only one, at worst length. If we took the best case as our measure of complexity, then all of the operations would have O(1) complexity. This is a rare case, however. What we want is the average case or worst case, which in this instance are the same: O(length). True, the average case would be O(length/2), but when we use order notation, O(length) and O(length/2) are equivalent. In some cases that we discuss later, the average and the worst cases are not the same.

InsertItem has two parts: (1) find the place to insert the item and (2) insert the item. In the unsorted list, the item is put in the length position and length is incremented. Neither of these operations depends on the number of items in the list, so the complexity is O(1).

DeleteItem also has two parts: (1) find the item to delete and (2) delete the item. Finding the item uses the same algorithm as RetrieveItem, so the complexity of that part is O(length). To delete the item, we put the value in the length - 1 position into the location of the item to be deleted and decrement length. These store and decrement tasks are not dependent on the number of items in the list, so this part of the operation has complexity O(l). The entire delete algorithm has complexity O(length) because O(length) plus O(l) is O(length). (Remember that O(l) is the goldfish.)

Sorted List ADT

Earlier, we considered three different algorithms for RetrieveItem. We said that the Unsorted List ADT algorithm would work for a sorted list but that two more efficient algorithms existed: a linear search in the sorted list that exits when it passes the place where the item would be and a binary search.

A linear search in a sorted list is faster than such a search in an unsorted list when we are seeking an item that is not in the list, but is the same when we are searching for an item that is in the list. Therefore, the complexity of the linear search in a sorted list is the same as the complexity in an unsorted list: O(length). Does that mean that we shouldn't bother taking advantage of the ordering in our search? No, it just means that the Big-O complexity measures are the same.

What about the binary search algorithm? Table 3.2 compared the number of items searched in a linear search versus a binary search for certain sizes of lists. How do we describe this algorithm using Big-O notation? To figure this problem out, let's see how many times we can split a list of N items in half. Assuming that we don't find the item we are seeking at one of the earlier midpoints, we have to divide the list log2N times at the most, before we run out of elements to split. In case you aren't familiar with logs,

That is, if N = 1,024, log2N = 10 (210 = 1024). How does that information apply to our searching algorithms? The sequential search is O(N); in the worst case, we would have to search all 1,024 elements of the list. The binary search is O(log2N); in the worst case, we would have to make log2N + 1, or 11, search comparisons. A heuristic (a rule of thumb) tells us that a problem that is solved by successively splitting it in half is an O(log2N) algorithm. Figure 3.9 illustrates the relative growth of the sequential and binary searches, measured in number of comparisons.

Click To expand
Figure 3.9: Comparison of linear and binary searches

InsertItem still has the same two parts: (1) finding the place to insert the item and (2) inserting the item. Because the list must remain sorted, we must search for the position in which to place the new item. Our algorithm used a linear search to find the appropriate location: O(length). Inserting requires that we move all those elements from the insertion point down one place in the array. How many items must we move? At most length, giving us O(length). O(length) plus O(length) is O(length) because we disregard the constant 2. Note, however, that the constant 2 does not actually occur here. In reality, we access each item in the list only once except for the item at the insertion point: We access those items to the place of insertion, and we move those items stored from length - 1 through that place. Therefore, only the element in the insertion location is accessed twice-once to find the insertion point and once to move it.

DeleteItem also still has the same two parts: (1) finding the item to delete and (2) deleting the item. The algorithm for finding the item is the mirror image of that for finding the insertion point: O(length). Deleting the item in a sorted list requires that all the elements from the deletion location to the end of the list be moved forward one position. This shifting algorithm is the reverse of the shifting algorithm in the insertion and, therefore, has the same complexity: O(length). Hence the complexity of the insertion and deletion algorithms is the same in the Sorted List ADT.

Table 3.4 summarizes these complexities. We have replaced length with N, the generic name for the size factor.

Table 3.4: Comparison of List Operations

Operation

Unsorted List

Sorted List

MakeEmpty

O(1)

O(1)

LengthIs

O(1)

O(1)

IsFull

O(1)

O(1)

ResetList

O(1)

O(1)

GetNextItem

O(1)

O(1)

RetrieveItem

O(N)

Linear search: O(N)

Binary search: O(log2N)

InsertItem

   
  • Find

O(1)

O(N)

  • Put

O(1)

O(N)

  • Combined

O(1)

O(N)

DeleteItem

   
  • Find

O(N)

O(N)

  • Remove

O(1)

O(N)

  • Combined

O(N)

O(N)

In the deletion operation, we could improve our efficiency by using the binary search algorithm to find the item to delete. Would this choice change the complexity? No, it would not. The find operation would be O(log2N), but the removal would still be O(N) because O(log2N) combined with O(N) is O(N). (Recall that the term with the largest power of N dominates.) Does this point mean that we should not use the binary search algorithm? No, it just means that as the length of the list grows, the cost of the removal dominates the cost of the find operation.

Think of the common orders of complexity as being bins into which we sort algorithms (Figure 3.10). For small values of the size factor, an algorithm in one bin may actually be faster than the equivalent algorithm in the next-more-efficient bin. As the size factor increases, the differences among algorithms in the different bins grows ever larger. When choosing between algorithms within the same bin, you should look at the constants to determine which to use.

Click To expand
Figure 3.10: Complexity bins


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)