14 practice sets · Page 1 of 1
What is the recurrence relation for the linear search recursive algorithm?
T(n-2)+c
2T(n-1)+c
T(n-1)+c
T(n+1)+c
Correct Answer: C — T(n-1)+c
Explanation:
After each call in the recursive algorithm, the size of n is reduced by 1. Therefore the optimal solution is T(n-1)+c.
Can linear search recursive algorithm and binary search recursive algorithm be performed on an unordered list?
Binary search can't be used
Linear search can't be used
Both cannot be used
Both can be used
Correct Answer: A — Binary search can't be used
Explanation:
As binary search requires comparison, it is required that the list be ordered. Whereas this doesn't matter for linear search.
What is the best case runtime of linear search(recursive) algorithm on an ordered set of elements?
O(1)
O(n)
O(logn)
O(nx)
Correct Answer: A — O(1)
Explanation:
The best case occurs when the given element to be found is at the first position. Therefore O(1) is the correct answer.
The array is as follows: 1,2,3,6,8,10. Given that the number 17 is to be searched. At which call it tells that there's no such element (By using linear search(recursive) algorithm)
7th call
9th call
17th call
The function calls itself infinite number of times
Correct Answer: A — 7th call
Explanation:
The function calls itself till the element is found. But at the 7th call it terminates as goes outside the array.
The array is as follows: 1,2,3,6,8,10. At what time the element 6 is found (By using linear search(recursive) algorithm)
4th call
3rd call
6th call
5th call
Correct Answer: A — 4th call
Explanation:
Provided that the search starts from the first element, the function calls itself till the element is found. In this case, the element is found in 4th call.
Linear search(recursive) algorithm used in _____________
When the size of the dataset is low
When the size of the dataset is large
When the dataset is unordered
Never used
Correct Answer: A — When the size of the dataset is low
Explanation:
It is used when the size of the dataset is low as its runtime is O(n) which is more when compared to the binary search O(logn).
What is the worst case runtime of linear search(recursive) algorithm?
O(n)
O(logn)
O(n^{2})
O(nx)
Correct Answer: A — O(n)
Explanation:
In the worst case scenario, there might be a need of calling the stack n times. Therfore O(n).
Is the space consumed by the linear search(recursive) and linear search(iterative) same?
No, recursive algorithm consumes more space
No, recursive algorithm consumes less space
Yes
Nothing can be said
Correct Answer: A — No, recursive algorithm consumes more space
Explanation:
The recursive algorithm consumes more space as it involves the usage the stack space(calls the function numerous times).
Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?
Both execute at same speed
Linear search(recursive) is faster
Linear search(Iterative) is faster
Cant be said
Correct Answer: C — Linear search(Iterative) is faster
Explanation:
The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling function and registering stacks repeatedly.
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
Correct Answer: B — Greater time complexities compared to other searching algorithms
Explanation:
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)
Correct Answer: D — O(1), O(n)
Explanation:
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)
Correct Answer: C — O(n)
Explanation:
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)
Correct Answer: D — O(1)
Explanation:
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
Correct Answer: D — When the list has only a few elements and When performing a single search in an unordered list
Explanation:
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.
