COM1201 Homework III Solution

1. (Orders of Magnitude)
Fill in the following table:

n	n3	n2	nlg(n)	lg(n)
10	1000	100	33.22	3.32
100	1000000	10000	664.39	6.64
1000	1000000000	1000000	9965.78	9.97
10000	1000000000000	100000000	132877.12	13.29
100000	1000000000000000	10000000000	1660964.05	16.61
1000000	1000000000000000000	1000000000000	19931568.57	19.93

where lg(n) is base 2.

2. (Big-O) Each of the functions shown below is to act on a dynamic set. For each function discuss Big-O of the number of comparisons (minimum, maximum, average) if:
a. The set is maintained as an unordered simply linked list.
b. The set is maintained as an ordered simply linked list.
c. The set is maintained as an ordered doubly linked list.

Note: I intended that x be passed by a pointer as in the last homework. My answers are based on that assumption. Assume the list has n elements.

• Search(S, k) returns pointer to element in S with key k if there is one,
  returns NULL otherwise
  a. unordered
  minimum - 1 compare if the first entry has key k - O(1)
  maximum - n compares if k is key of the last element or k is not in the list - O(n)
  average - n/2 compares for k in list - O(n)
  The actual average depends on the probability that a key searched for is appears in the list.
  b. ordered - simple
  minimum - 1 compare if the first entry has key k - O(1)
  maximum - n compares if k is key of the last element or k is not in the list - O(n)
  average - n/2 compares for k in list - O(n)
  The actual average depends on the probability that a key searched for is appears in the list.
  c. ordered - double
  minimum - 1 compare if the first entry has key k - O(1)
  maximum - n compares if k is key of the last element or k is not in the list - O(n)
  average - n/2 compares for k in list - O(n)
  The actual average depends on the probability that a key searched for is appears in the list.

• Minimum(S) returns pointer to element in S with minimum key
  returns NULL if S is empty
  a. unordered
  minimum = maximum = average = n , so O(n).
  Must always check the entire list.
  b. ordered - simple
  minimum = maximum = average = 0, just return first element.
  c. ordered - double
  minimum = maximum = average = 0, just return first element.>

• Successor(S, x) returns pointer to element after x in S, ordered by k
  returns NULL if x is last element
  a. unordered
  minimum = maximum = average = n , so O(n).
  Must always check the entire list.
  b. ordered - simple
  minimum = maximum = average = 0, just return next element ((&x)->next).
  c. ordered - double
  minimum = maximum = average = 0, just return next element ((&x)->next).

• Predecessor(S, x) returns pointer to element before x in S, ordered by k
  returns NULL if x is first element
  a. unordered
  minimum = maximum = average = n , so O(n).
  Must always check the entire list.
  b. ordered - simple
  pretty much like search.
  minimum - 1 if no predecessor - O(1)
  maximum - n 1 to see if list is empty, n-1 to get to next to lest position - O(n)
  Average - n/2 - O(n)
  Must start ptr at the front of the list and advance until ptr->next = &x. The compares are compares of pointers, not of keys.
  c. ordered - double
  minimum = maximum = average = 0, just return last element ((&x)->last).

• Insert(S, x) // Assume x is initialized and a pointer is passed
  a. unordered
  No compares - O(0), just insert at head.
  b. ordered - simple
  Insert(S, x) - Same as for Predecessor then just move pointers.
  c. ordered - double
  As for Search, must find the right place for the new element then move pointers to insert.>

• Delete(S, x) // Given a pointer to x, remove that element from the set
  a. unordered
  minimum - 1 compare if the first entry has key k - O(1)
  maximum - n compares if k is key of the last element or k is not in the list - O(n)
  average - n/2 compares for k in list - O(n)
  Like search but must compare pointers, not keys to find the previous element in the list, NOT the predecessor by key.
  b. ordered - simple
  Insert(S, x) - Same as for Predecessor then just move pointers.
  c. ordered - double
  O(0). Just move pointers.

Last Updated: April 16, 1997 12:29 pm by