1.4 Time and space complexities

Question 1

What is the time and space complexity of linear search?

Answer 1

The time and space complexity of a linear search are as follows:

Time Complexity
- Best Case: ( O(1) ) — The best case occurs when the element being searched for is the first element in the array.
- Worst Case: ( O(n) ) — The worst case occurs when the element is the last element in the array or not present at all, requiring the algorithm to traverse the entire array.
- Average Case: ( O(n) ) — On average, the search must check half of the elements in the array.

Space Complexity
- Space Complexity: ( O(1) ) — Linear search uses a constant amount of extra space since it only requires a single additional variable to hold the index of the current element being compared.

Thus, linear search is efficient in terms of space but not as efficient in terms of time, especially for large data sets.

Question 2

What is the time and space complexity of binary search?

Answer 2

The time and space complexity of binary search are as follows:

Time Complexity
- Best Case: ( O(1) ) — The best case occurs when the target element is the middle element of the array.
- Worst Case: ( O(\log n) ) — The worst case occurs when the search has to repeatedly halve the search space until it is reduced to a single element.
- Average Case: ( O(\log n) ) — On average, the search will have to traverse approximately half the height of the binary search tree, leading to a logarithmic time complexity.

Space Complexity
- Iterative Version: ( O(1) ) — The iterative implementation of binary search requires a constant amount of extra space for variables used to track the current search range.
- Recursive Version: ( O(\log n) ) — The recursive implementation requires space proportional to the height of the recursion stack, which corresponds to the depth of the binary search tree and is ( \log n ) in the worst case.

In summary, binary search is efficient in terms of time for sorted arrays, with a logarithmic time complexity, but its space complexity can vary depending on whether it is implemented iteratively or recursively.

Question 3

What is the time and space complexity of bubble sort?

Answer 3

The time and space complexity of bubble sort are as follows:

Time Complexity
- Best Case: ( O(n) ) — The best case occurs when the array is already sorted. In this scenario, a single pass through the array confirms that no swaps are needed, resulting in a linear time complexity.
- Worst Case: ( O(n^2) ) — The worst case occurs when the array is sorted in reverse order, requiring the algorithm to perform ( n-1 ) passes, with each pass performing ( n-i-1 ) comparisons (where ( i ) is the current pass number).
- Average Case: ( O(n^2) ) — On average, bubble sort requires multiple passes through the array, leading to a quadratic time complexity.

Space Complexity
- Space Complexity: ( O(1) ) — Bubble sort is an in-place sorting algorithm, meaning it requires only a constant amount of extra space for swapping elements.

In summary, bubble sort has a quadratic time complexity, making it inefficient for large datasets, but it is space-efficient since it operates in-place.

Question 4

What is the time and space complexity of quick sort?

Answer 4

The time and space complexity of quicksort are as follows:

Time Complexity
- Best Case: ( O(n \log n) ) — The best case occurs when the pivot element chosen divides the array into two nearly equal halves, resulting in a balanced partition.
- Worst Case: ( O(n^2) ) — The worst case occurs when the pivot element is the smallest or largest element, leading to highly unbalanced partitions. This can happen if the array is already sorted or nearly sorted and the first or last element is chosen as the pivot.
- Average Case: ( O(n \log n) ) — On average, quicksort performs well with random pivot selection, dividing the array into two parts of roughly equal size.

Space Complexity
- Space Complexity:
- In-Place Version: ( O(\log n) ) — The in-place version of quicksort uses recursive function calls that require space proportional to the height of the recursion tree, which is ( \log n ) for a balanced partition.
- With Extra Storage: If an auxiliary array is used for partitioning, the space complexity would increase to ( O(n) ), but this is uncommon in practical implementations.

In summary, quicksort is efficient for average cases with a time complexity of ( O(n \log n) ) and has a relatively low space complexity of ( O(\log n) ) for the in-place version. However, its worst-case time complexity is ( O(n^2) ), though this can be mitigated by using strategies like randomizing the pivot selection.