Write linear/sequential search algorithm and calculate time and space complexity on it.
- अरुण कुमार
- 0
- Posted on
Course: M.C.A. (REVISED) B.C.A. (REVISED)
Term-End Examination
Year: June, 2020
Subject: MCS-021 : DATA AND FILE STRUCTURES
Below is a simple implementation of the linear/sequential search algorithm in Python, along with an explanation of its time and space complexity.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Return the index where the target is found
return -1 # Return -1 if the target is not found in the array
Example usage
arr = [4, 2, 7, 1, 9, 5]
target = 7
result = linear_search(arr, target)
if result != -1:
print(f”Target {target} found at index {result}”)
else:
print(f”Target {target} not found in the array”)
Time Complexity: In the worst-case scenario, the linear search algorithm needs to iterate through the entire array to find the target element or determine that it’s not present. This results in a time complexity of O(n), where n is the number of elements in the array.
Space Complexity: The space complexity of the linear search algorithm is O(1), constant space. This is because the algorithm uses only a fixed amount of extra space to store variables (like the loop counter and target), regardless of the size of the input array.
It’s important to note that the linear search algorithm is not the most efficient search algorithm, especially for large arrays, as its time complexity grows linearly with the size of the array. Other search algorithms like binary search (for sorted arrays) or hash-based search (for specific use cases) offer better time complexity in certain scenarios.