NIELIT 2021 Dec Scientist A - Section B: 117

Question

Worst case scenario in case of linear search algorithm is ______________ .

• A. Item is somewhere in the middle of the array.
• B. Item is not in the array at all.
• C. Item is the last element in the array.
• D. Item is the last element in the array or is not there at all.

Answer 1

Answer is D

If an item is in the last place or not present in array then Linear search  algorithm have to check each element from the beginning and in the worst case it might be found as last element or possibility of not found.

 

Answer 2

Correct Answer Option B

Option A = False :- We Will Stop Midway Hence not covering the Whole Array 

Option B = True :- We Will Have to Traverse till the end of the array .

Option C = False :- We don’t need to Traverse till the end  We can just Check by using a simple conditional statement .

Option D = False :- ( Can Be True But Here is why i think its False ) → Option D still covers the Option C and we know Option C isnt the worst Case scenario . 

Comments

in option B and C number of comparisons are n, so definitely C is not false. D seems more correct answer as it covers both the cases.

---

and you said "We don't need to traverse till the end We can just Check by using a simple conditional statement" what conditional statement you'll write?

---

@0z4rk in Option C i think it wont be the correct explanation because we need to use Linear search only and accessing the array randomly is not allowed 

what you are doing here is accessing the last element directly which is random access 

Answer 3

Lets assume an array A = [2,5,1,4,7]

Lets understand all the options,

• A. 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)
• B. 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)
• C. 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)
• D. 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,

• A. It would be the same O(n)
• B. It would also be the same O(n)
• C. Here, it would just need one check as we would see if the last element is our required element or not so O(1)
• D. It would again be O(n)