RMP MCA-22.01.24-searching and sorting-FN

Which of the following is correct recurrence for worst case of Binary Search?

• T(n) = 2T(n/2) + O(1) and T(1) = T(0) = O(1)
• T(n) = T(n-1) + O(1) and T(1) = T(0) = O(1)
• T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1)
• T(n) = T(n-2) + O(1) and T(1) = T(0) = O(1)

What is the time complexity of binary search with iteration?

• O(nlogn)
• O(logn)
• O(n)
• O(n2)

Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found using Binary Search?

• 1
• 3
• 4
• 2

Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion using Binary Search?

• 5
• 2
• 3
• 4

What is the worst case complexity of binary search using recursion?

• O(n log n)
• O(log n)
• O(n)
• O(n2)

Which of the following is not a limitation of binary search algorithm?

• must use a sorted array
• requirement of sorted array is expensive when a lot of insertion and deletions are needed
• there must be a mechanism to access middle element directly
• binary search algorithm is not efficient when the data elements are more than 1500

The Average case occurs in linear search algorithm _____________

• when item is somewhere in the middle of the array
• when item is not the array at all
• when item is the last element in the array
• Item is the last element in the array or item is not there at all

Binary search algorithm cannot be applied to ___________________.

• sorted linked list
• sorted binary trees
• sorted linear array
• pointer array

Complexity of linear search algorithm is ________________.

• O(n)
• O(logn)
• O(n2)
• O(n logn)

Which of the following is not the required condition for binary search algorithm?

• The list must be sorted
• There should be the direct access to the mid element in any sub list
• There must be mechanism to delete and/or insert elements in list.
• Number values should only be present