Determine the time and space complexities of a linear search.

Question

Time complexity :O(log(n)) Space complexity O(n)
Time complexity :O(n) Space complexity O(log(n))
Time complexity :O(n) Space complexity O(n)
Time complexity O(log(n)) Space complexity O(log(n))

Answer 1

The correct time and space complexities of a linear search algorithm are:
Time complexity: O(n)
Space complexity: O(1)

In a linear search, we iterate through each element in the input sequentially until we find the desired element or reach the end of the list. In the worst case scenario, where the desired element is at the end of the list or does not exist in the list at all, we would have to iterate through all n elements of the list, making the time complexity O(n).

The space complexity is O(1) because we only need a constant amount of space to store the index or pointer to the current element we are checking. No additional space is required as the size of the input increases.