Problem Statement
What is the time complexity of linear search in the worst case?
Explanation
Linear search has worst-case time complexity of O of n because in the worst case, you need to check every element in the array. This happens when the target element is at the last position or not present in the array.
Linear search examines each element sequentially from the beginning until it finds the target or reaches the end. Best case is O of 1 when the element is at the first position. Average case is O of n divided by 2 which simplifies to O of n. Linear search works on both sorted and unsorted arrays, unlike binary search which requires sorted data.
Code Solution
SolutionRead Only
// Linear Search - O(n) worst case
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i; // Found at index i
}
return -1; // Not found after checking all n elements
}
// Example: [5, 2, 8, 1, 9]
// Search 9: Check 5, 2, 8, 1, 9 - found at index 4
// Search 7: Check all 5 elements - not found
// Best case: O(1) - element at index 0
// Average case: O(n/2) = O(n)
// Worst case: O(n) - element at last or not present