Question

Consider a circular array contains integers that are sorted in descending order. Additionally, consider a linear search algorithm that randomly decides to search the array either starting from its start (index 0 ) or from its end (index n−1 ). The worst casc of this search algorithm for a value x occurs when: A. x is at either end of the array B. x is in the middle of the array C. x is not in the array at all, or it is located at either end D. x is smaller than the value located at index 0 E. x is larger than the value located at index n−1 vii) Consider an ADT has the following methods: - inser(e): Inserts element e at the start of the collection - remove(e): Deletes element e from the collection - search(e): Searches for an element e in the collection Additionally, it is expected that insertions in the list will be massive (done quite often). where removal and search are to be done rarely. Further, the ADT is expected to be employed in system with very critical space limitations (space is very limited; and hence space complexity is a priority). Under these conditions: A. It is better to use expandable non-circular arrays as the underlying data structure of this ADT B. It is better to use expandable circular arrays as the underlying data structure of this ADT C. It is better to use heaps as the underlying data structure of this ADT D. It is better to use singular linked lisss underlying data structure of this ADT E. It is better to use doubly linked lists underlying data structure of this ADT viii) Consider the use of binary recursion by a method called multiplyarr (A,i,n), which accepts an array of integers, A, a starting index, i, and a number of elements, n. The method computes the total value (the product) resulting from multiplying all n elements of the array starting from index i. Precisely, the method returns A[i] if n=1; otherwise it recursively retums (the multiplied value of the left half of the array) ⋅ (the multiplied value of the right half of the array). If n is odd, then the left half is larger by one element. The number of needed calls for the method to finish will result in: A. Time complexity of O(n

2
) and stack growth of O(n
2
). B. Time complexity of O(n
2
) and stack growth of O(n). C. Time complexity of O(n) and stack growth of O(logn). D. Exponential time complexity of O(2
n
) but stack growth of O(n
2
). E. None of the above answers is correct.

Answer 1

The worst case for a linear search in a sorted descending circular array occurs when x is not in the array or at either end; a singly linked list is the best choice for an ADT with frequent insertions and space constraints; and the multiplyarr method has a time complexity of O(n) with stack growth of O(log n).

Step-by-step explanation:

The worst case scenario for a linear search algorithm in a circular array that is sorted in descending order, when searching for a value x, happens when x is not in the array at all, or it is located at either end of the array. This is due to the fact that the algorithm would have to traverse the entire array to determine that the item is not present or to find it at the very end of the search path.

For an Abstract Data Type (ADT) that requires frequent insertions at the start of the collection and is subject to very critical space limitations, it is generally better to use a singly linked list. Singly linked lists are ideal because they have a minimal overhead, with only one pointer needed per node, and they allow for constant-time insertions at the start.

The method multiplyarr uses binary recursion to calculate the product of elements in an array. This method exhibits a time complexity of O(n), because it reduces the problem size by half with each recursive call, eventually leading to the base case when n=1. The stack growth, which is indicative of the recursion depth, has a complexity of O(log n), as the height of the recursion tree grows logarithmically with the number of elements in the array.