CSC148 Summer 1996 Assignment 3 Solution to the analysis section (part II): ------------------------------------------- Let n be the number of members of the Rhinoceros party. Space requirements: A. The array implementation requires space to store a record for each member. It also requires extra space to allow the membership list to grow. Because each record needs 200-300 bytes to store all the information in the record, it may need more total space than the other three implementations. For example, if we need 10% extra space to allow for membership growth, we will "waste" 0.1*N*300 = 30N bytes of space, where N is the number of members, and we assume each record takes roughly 300 bytes. Each pointer is 8 bytes, so if an implementation had 4 pointers per record, it would require approximately the same amount of space as an array with 10% extra space. Note that if we need more than 10% extra space for the array, the array implementation will require more memory. B. The circular linked list needs memory for each member plus memory for two pointers. C. The linked list with threaded city, needs memory for each member record plus memory for two pointers, plus an array to store the pointers to the city threads. Therefore it requires a more memory than option B. D. The linked list with threaded postal code, date of last received membership fee, and amount of last received donation, needs four pointers in addition to the member record space. I will assume that each thread is ordered and does not use an extra array for different starting points within each thread. Options B and C require the least memory. Depending on how much extra space is required for the array, option A or D will require the most memory. General notes: ------------- 1. There are several options any time we need to sort our members for initializing or printing. If we use insertion sort or selection sort, the runtime will be O(n^2), but we will not need any extra memory. If we use a more efficient sorting algorithm such as quick sort or merge sort, we will need extra memory (up to the size of list itself) to store intermediate stages. Throughout the following discussion, I will assume merge sort and extra memory are used when ever sorting is required. Runtime of each operation: ------------------------- 1. Initialize data structure: A: Since the array is to be sorted by surname and we don't know how the data is organized in the file, we must sort the records as we insert them into the array -- O(nlogn). B: Since the list does not need to be sorted we can insert each member at the beginning of the list. Therefore, the runtime of this operation is O(n). C: Again, we must sort the members by surname, so the time to initialize the list will be O(nlogn). We must also initialize the cities thread. For each member we will search the city array to find the matching city -- O(k) where k is the number of cities (k < n), then insert the city into the thread -- O(1) because the order of members within the thread does not matter. Therefore the total time is O(nlogn + k) = O(nlogn). D: In this implementation we must insert each member into four sorted lists, so the total runtime for this operation is O(4nlogn) = O(nlogn). (Unlike option C, each of the four threads is sorted.) 2. Add a new member: A: We must find the place to insert the record (O(logn) if we use binary search),and then shift all the remaining records down to make space for the new record (O(n)). The total is O(logn + n) = O(n). B: Since the list is not sorted, we can add the new record at the beginning -- O(1). This is the fastest implementation. C: We must find the place to insert the record, but we cannot use binary search -- O(n). Doing the insert takes O(1). We must also connect the city thread -- O(k) to find the city in the array plus O(1) to add the record to the city thread. Therefore, the total is O(n + k). D: As in C, it takes O(n) to insert the member in surname order. Then we must connect each of the three remaining threads. Because each thread is sorted it will take O(n) to add the new member to each thread. Therefore the total time is O(4n) = O(n). This operation will take the longest (on average) using this implemenation. 3. Delete a member: A: The same process as adding a new member is required so the total time is O(logn + n) = O(n). B: We must find the record before we can delete it -- O(n). C: Deleting a member takes the same time as adding it in this case. Therefore the total time is O(n + k). D: As in C, the time for adding is the same as the time for deleting. The total time is O(4n) = O(n). This option requires the longest runtime in the worst case. 4. Print all members in a certain province: All four options take O(n) for this operation because we must traverse the entire list of members to print the members in a certain province. Traversing a linked list takes a little longer than traversing an array because we must read the value of the pointer. Each of the three linked lists will take the same time. 5. Print all members in a certain city: Options A, B, and D take the same time for the same reasons as in 4 -- O(n). C: Because the list is threaded by city, we need to search the array of cities (O(k) or O(logk)). Then we can follow the city thread printing out each member in the thread -- O(p) where p is the number of members in a city). The runtime is O(k + p). Note that k < n and p < n. Because we don't need to visit each member of the list to print out the members from one city, this implementation will run faster than the other three. 6. Print all members whose total donations exceed a certain amount. All implementations take the same amount of time because none of them have been threaded for total donations -- O(n). The argument is the same as in 4. 7. Print all members whose last received donation exceeds a certain amount. A, B, C: These implementations take O(n) for the same reasons as in 6. D: This implementation has a thread for last received donation, and if we were smart enough to order it in decreasing order, we can just start printing each member on the thread until we reach a member whose donations are lower than the given amount. Note that although this implementation still takes O(n) time, it will run faster than the other three implementations because not every node needs to be visited. If we ordered the thread in increasing order, the operation will take exactly as long as the other three implementations. 8. Print a list ordered by postal code, of all members who have not paid their dues within the last year. A, B, C: We must sort the list by postal code and find all members who have not paid their dues. -- O(n + nlogn) = O(nlogn). D: Because this implementation has a thread ordered by postal code, we can traverse the thread, printing out members that haven't paid their dues. The runtime for this operation is O(n). Conclusion: ---------- There is no clear winner among the implementations. The circular linked list has the best performance for initializing and adding members. The array is better when a traversal is needed. The threads provided by options C and D improve the runtime ofoperation that depend on the order of threaded elements. Ordering the list by surname does not seem to be useful since none of operations that retrieve membership information use the surname order. If members are not added or deleted very often, but lists of members are created ordered by different fields of the record, then the options with threads perform the best (as long as the extra space for pointers is feasible).