ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
In which of the cases uniform binary search fails compared to binary search?
A table lookup is generally faster than an addition and a shift
Many searches will be performed on the same array
Many searches will be performed on several arrays of the same length
Complexity of code
Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.
Which of the following is a disadvantage of linear search?
Requires more space
Greater time complexities compared to other searching algorithms
Not easy to understand
Not easy to implement
The complexity of linear search as the name suggests is O(n) which is much greater than other searching techniques like binary search(O(logn)). Linear search is easy to implement and understand than other searching techniques.
What is the best case and worst case complexity of ordered linear search?
O(nlogn), O(logn)
O(logn), O(nlogn)
O(n), O(1)
O(1), O(n)
Although ordered linear search is better than unordered when the element is not present in the array, the best and worst cases still remain the same, with the key element being found at first position or at last position.
What is the worst case for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
Worst case is when the desired element is at the tail of the array or not present at all, in this case you have to traverse till the end of the array, hence the complexity is O(n).
What is the best case for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
The element is at the head of the array, hence O(1).
Where is linear searching used?
When the list has only a few elements
When performing a single search in an unordered list
Used all the time
When the list has only a few elements and When performing a single search in an unordered list
It is practical to implement linear search in the situations mentioned in When the list has only a few elements and When performing a single search in an unordered list, but for larger elements the complexity becomes larger and it makes sense to sort the list and employ binary search or hashing.
What is the time complexity of Jump Search?
O(logn)
O(n)
O(sqrt(n))
O(nlogn)
Since the size of the step is sqrt(n), the complexity is also obviously O(sqrt(n)).
What is the length of the step in jump search?
n
n/2
sqrt(n)
1
If the step size is 1, it becomes a linear search, if it is n, we reach the end of the list in just on step, if it is n/2, it becomes similar to binary search, therefore the most efficient step size is found to be sqrt(n).
Which of the following is not an advantage of Fibonacci Search?
When the element being searched for has a non uniform access storage
Can be used in magnetic tapes
Can be used for large arrays which do not fit in the CPU cache or in the RAM
It can be applied efficiently on unsorted arrays
When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion. Fibonacci search won't work on unsorted arrays. The input should be a sorted array or array should be sorted before Fibonacci search.
What is the time complexity of Fibonacci Search?
O(logn)
O(n)
O(n^{2})
O(nlogn)
Since it divides the array into two parts, although not equal, its time complexity is O(logn), it is better than binary search in case of large arrays.
Choose the recursive formula for the Fibonacci series.(n>=1)
(F(n) = F(n+1) + F(n+2))
(F(n) = F(n) + F(n+1))
(F(n) = F(n-1) + F(n-2))
(F(n) = F(n-1) - F(n-2))
None.
Which algorithmic technique does Fibonacci search use?
Brute force
Divide and Conquer
Greedy Technique
Backtracking
With every iteration, we divide the given array into two sub arrays(not necessarily equal).
What is the time complexity of binary search with iteration?
O(nlogn)
O(logn)
O(n)
O(n^{2})
(T(n) = T(n/2) + theta(1))
Using the divide and conquer master theorem, we get the time complexity as O(logn).
Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations?
90 and 99
90 and 100
89 and 94
94 and 99
Trace the input with the binary search iterative code.
Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
1
3
4
2
Iteration1 : mid = 77; Iteration2 : mid = 88;
Binary Search can be categorized into which of the following?
Brute Force technique
Divide and conquer
Greedy algorithm
Dynamic programming
Since 'mid' is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.
Which of the following is not an application of binary search?
To find the lower/upper bound in an ordered sequence
Union of intervals
Debugging
To search in unordered list
In Binary search, the elements in the list should be sorted. It is applicable only for ordered list. Hence Binary search in unordered list is not an application.
What is the average case time complexity of binary search using recursion?
O(nlogn)
O(logn)
O(n)
O(n^{2})
T(n) = T(n/2) + 1, Using the divide and conquer master theorem.
What is the worst case complexity of binary search using recursion?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Using the divide and conquer master theorem.
Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
90 and 99
90 and 94
89 and 99
89 and 94
At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.
