1. Where is linear searching used?
a) When the list has only a few elements
b) When performing a single search in an unordered list
c) Used all the time
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.
2. What is the best case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Explanation: The element is at the head of the array, hence O(1).
3. What is the worst case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
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).
4. What is the best case and worst case complexity of ordered linear search?
a) O(nlogn), O(logn)
b) O(logn), O(nlogn)
c) O(n), O(1)
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.
5. What does the following piece of code do?
for (int i = 0; i < arr.length-1; i++)
{
for (int j = i+1; j < arr.length; j++)
{
if( (arr[i].equals(arr[j])) && (i != j) )
{
System.out.println(arr[i]);
}
}
}
a) Print the duplicate elements in the array
b) Print the element with maximum frequency
c) Print the unique elements in the array
d) Prints the element with minimum frequnecy
Explanation: The print statement is executed only when the items are equal and their indices are not.
6. Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) Not easy to implement
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.
7. Is there any difference in the speed of execution between linear search(recursive) vs linear search(lterative)?
a) Both execute at same speed
b) Linear search(recursive) is faster
c) Linear search(Iterative) is faster
d) Cant be said
Explanation: The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling function and registering stacks repeatedly.
8. Is the space consumed by the linear search(recursive) and linear search(iterative) same?
a) No, recursive algorithm consumes more space
b) No, recursive algorithm consumes less space
c) Yes
d) Nothing can be said
Explanation: The recursive algorithm consumes more space as it involves the usage the stack space(calls the function numerous times).
9. What is the worst case runtime of linear search(recursive) algorithm?
a) O(n)
b) O(logn)
c) O(n2)
d) O(nx)
Explanation: In the worst case scenario, there might be a need of calling the stack n times. Therfore O(n).
10. Linear search(recursive) algorithm used in _____________
a) When the size of the dataset is low
b) When the size of the dataset is large
c) When the dataset is unordered
d) Never used
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).
Design and Analysis of Algorithms
The Quest for the Right Element
Imagine you're at a library, searching for that one book that holds the answer to all your questions. Linear search is like being a meticulous librarian, scanning each shelf one by one until you lay your hands on the elusive tome.
Linear search is the algorithmic equivalent of a sequential investigation. It's like looking for your keys – you check each pocket until you triumphantly declare, "Eureka!"
Why Linear, You Ask?
Linear search might not be the rockstar of algorithms, but it has its moment in the spotlight. You have an unordered list, and you need to find a specific element. Linear search steps in, traversing the list like a detective on a mission.
It's the go-to method when you're dealing with a small-scale scavenger hunt. Efficient? Not for colossal datasets. But for a cozy little array, it's your trusty sidekick.
Designing the Search Party
In the grand carnival of algorithms, Linear Search stands out for its simplicity. No complex choreography, no dazzling acrobatics – just a straightforward pursuit of the target.
When designing algorithms, especially for MCQ scenarios in Design and Analysis, linear search gets its moment under the spotlight. It's the friendly neighbor you can rely on for a cup of sugar or finding that pesky bug in your code.
Wrapping It Up
So, there you have it – Linear Search, the modest hero in the algorithmic saga. It might not make headlines, but it's an indispensable part of the design and analysis party, especially when tackling MCQ challenges. As we bid adieu to our algorithmic adventure, remember: sometimes, the simplest path leads to the most profound discoveries. Happy coding, fellow algorithm explorers!