Lets assume an array A = [2,5,1,4,7]
Lets understand all the options,
- If we want to search for 1 using linear search, then we must go linearly so Time Complexity would be O(n/2) = O(n)
- If we want to search for 8 using linear search, then it would go until the last of the array and print a “not found” message so Time Complexity would be O(n)
- If we want to search for 7 using linear search, then it would directly go until the end so Time Complexity would be O(n)
- If we want to search for either 7 or 8 then whatsoever it is, it would go until the end and traverse the entire array ONLY ONCE but completely traverse so Time Complexity would be O(n) again.
So, as per my idea, All options would be correct (if it is an MSQ)
Now, if we choose to traverse the array in reverse,
- It would be the same O(n)
- It would also be the same O(n)
- Here, it would just need one check as we would see if the last element is our required element or not so O(1)
- It would again be O(n)