Complexity Analysis for Grid class Analyze the best casewors

Complexity Analysis for Grid class Analyze the best case/worst case complexity for specified member function of SingleLinkedList class on page 2 by selecting the best fit expressions. Assume that when each specified method is invoked by an instance of SingleLinkedList calss, there are n items in it. The complexity of the best case of the searchIndex method: ______________ O(1) Theta(n) Theta(n^2) Ohm(n) Ohm(n^2) The complexity of the worst case of the searchIndex method:_____________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the best case of the insert2End method:________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the best case of the delete method: ___________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the worst case of the delete method: __________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the best case of the deleteFromHead method:___________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the worst case of the deleteFromHead method: ___________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the best case of the deleteFromEnd method: _____________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2) The complexity of the worst case of the deleteFromEnd method: __________ The complexity of the best case of the ______ str ______ method:____________ O(1) Theta(n) Theta (n^2) Ohm(n) Ohm(n^2)

Solution

Please follow the data and description :

The term best-case performance is used in the stream of the computer science as to describe an algorithm\'s behavior under the optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.

16) searchIndex : It is used to search for an index in the given value from the user. The complexity for this method in the best case for there are n items is OPTION B ((n)).

17) For the same method the worst case is also the same OPTION B (O(n)).

18) insert2End : This method is used to enter the element or to insert the element to the end of the list. So the complexity in the best case is given as (1). So the answer is OPTION A ((1)).

19) delete : This method is used to delete an element desired by the user based on the index values. So the complexity of the algorithm is given as (1). So the answer is OPTION A ((1)).

20) For the same method the worst case is given as O(1). So the answer is OPTION A (O(1)).

21) deleteFromHead : This method is used to delete an element from the head based on the index values. So the complexity of the algorithm is given as (1). So the answer is OPTION A ((1)).

22) For the same method the worst case is given as O(1). So the answer is OPTION A (O(1)).

23) deleteFromEnd : This method is used to delete an element from the end based on the index values. So the complexity of the algorithm is given as (1). So the answer is OPTION A ((1)).

24) For the same method the worst case is given as O(1). So the answer is OPTION A (O(1)).

25) str : This method is to print the data to string to console. So the complexity is given by (n) for n elements. So the answer is OPTION B ((n)).

NOTE :

In order to delete a node and connect the previous and the next node together, we need to know their pointers. In a doubly-linked list, both pointers are available in the node that is to be deleted. The time complexity is constant in this case, i.e., O(1).

Hope this is helpful.