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

n	n3	n2	nlg(n)	lg(n)
10
100
1000
10000
100000
1000000

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:

• Search(S, k) returns pointer to element in S with key k if there is one, returns NULL otherwise
• Minimum(S) returns pointer to element in S with minimum key returns NULL if S is empty
• Successor(S, x) returns pointer to element after x in S, ordered by k returns NULL if x is last element
• Predecessor(S, x) returns pointer to element before x in S, ordered by k returns NULL if x is first element
  
• Insert(S, x) // Assume x is initialized and a pointer is passed
  
• Delete(S, x) // Given a pointer to x, remove that element from the set

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:

Last Updated: April 6, 1997 9:22 pm by