2. Determine the time and space complexities of a linear search
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(n)
time complexity: O(log(n))
space complexity: O(log(n))
The correct answer is:
time complexity: O(n)
space complexity: O(1)
The correct answer is:
- Time complexity: O(n)
- Space complexity: O(1)
Explanation:
In a linear search, we iterate through each element of the array or list until we find the desired element or reach the end of the collection. The time complexity is determined by the number of elements, n, in the collection. In the worst case scenario, where the desired element is at the end of the collection or not present at all, we need to iterate through all the elements. Hence, the time complexity is O(n), where n is the size of the collection.
Regarding space complexity, it refers to the amount of additional memory required by the algorithm. In the case of a linear search, we do not require any additional memory proportional to the input size (n). We only need a few temporary variables to hold the current index, the element we are comparing, and the result. Thus, the space complexity is O(1), constant and independent of the input size.
The correct answer is:
time complexity: O(n)
space complexity: O(1)
In a linear search, also known as sequential search, each element in the list is compared with the target element until a match is found or the end of the list is reached. The time complexity of a linear search is O(n) because the worst-case scenario occurs when the target element is located at the end of the list or not present at all, requiring n comparisons.
The space complexity of a linear search is O(1) because only a few constant amount of temporary variables are required to store the index and comparison results during the execution of the algorithm. No additional space is needed as the size of the input grows.