Performance Comparison: SortedListAsArray vs. SortedListAsList

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Performance Comparison: `SortedListAsArray` vs. `SortedListAsList`

The running times calculated for the various member functions of the two sorted list implementations, SortedListAsArray and SortedListAsLinkedList, are summarized below in Table . With the exception of two member functions, the running times of the two implementations are asymptotically identical.

sorted list implementation

member function
SortedListAsArray SortedListAsLinkedList

Insert O(n) O(n)

IsMember O(n) O(n)

Find O(n)

FindPosition O(n)

Withdraw O(n) O(n)

Table: Running Times of Operations on Sorted Lists

**Table:** Running Times of Operations on Sorted Lists
	sorted list implementation
member function	`SortedListAsArray`	`SortedListAsLinkedList`
`Insert`	O(n)	O(n)
`IsMember`	O(n)	O(n)
`Find`		O(n)
`FindPosition`		O(n)
`Withdraw`	O(n)	O(n)

Neither the SortedListAsArray nor SortedListAsLinkedList implementations required any additional member variables beyond those inherited from their respective base classes, ListAsArray and ListAsLinkedList. Consequently, the space requirements analysis of the sorted list implementations is identical to that of the ordered list implementations given in Section .