Question

Please post all code in Pseudo code. Please post ORIGINAL answers do not copy from similar questions. Please post in a format that can be directly copied. Reasoning on answers would be most helpful but not required. Thank you in advance for your help.

1. List the following functions according to their order of growth from the lowest to the highest:

(n−2)!,

5lg(n+100)10,

22n,

0.001n4 +3n3 +1,

ln2 n,

√3 n,

3n.

2. The range of afinite nonempty set of n realnumbers S is defined as the differ- ence between the largest and smallest elements of S. For each representation of S given below, describe in English an algorithm to compute the range. Indi- cate the time efficiency classes of these algorithms using the most appropriate notation (O, ?Omega, or ?).

a. An unsorted array
b. A sorted array
c. A sorted singly linked list

d. A binary search tree

Answer 1

1

5lg(n+100)10,

ln2 n,

√3 n,

0.001n4 +3n3 +1,

3n,

22n,

(n−2)!.

2

a. An unsorted array:

Algorithm:

• Initialize two variables namely min and max to 9999 and -9999 respectively
• Traverse through the array until we find min and max
• print the difference between max and min

Time complexity is O(n)

b. A sorted array:

Algorithm:

• As the array is already sorted store the first element in min and last element in max
• print the difference between max and min

Time complexity is O(1)

c. A sorted single linked List:

Algorithm:

• As the linked list is already sorted, store the first element of the list in min and the last element in max.
• print the difference between min and max

Time complexity is O(1)

d. A binary search tree

Algorithm:

• Traverse until the Left most element is reached and store the value in min.
• Traverse until the Right most element is reached and store the value in max.
• print the difference between max and min

Time complexity is O(n)

Hope this helps