Determine the time and space complexities of a merge sort.(1 point)

Question

Responses

time complexity: O(n⋅log(n))

space complexity: O(n⋅log(n))
time complexity: upper O left parenthesis n times log left parenthesis n right parenthesis right parenthesis space complexity: upper O left parenthesis n times log left parenthesis n right parenthesis right parenthesis

time complexity: O(n)

space complexity: O(n⋅log(n))
time complexity: upper O left parenthesis n right parenthesis space complexity: upper O left parenthesis n times log left parenthesis n right parenthesis right parenthesis

time complexity: O(n2)

space complexity: O(n)
time complexity: upper O left parenthesis n squared right parenthesis space complexity: upper O left parenthesis n right parenthesis

time complexity: O(n⋅log(n))

space

Answer 1

The correct time and space complexities for the merge sort algorithm are as follows:

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Explanation:

1. Time Complexity:

   • Merge sort works by dividing the array into halves recursively until each sub-array contains a single element (log n divisions). Then, it merges the sub-arrays back together in a sorted manner, which takes linear time (O(n)) for each level of recursion. Thus, the overall time complexity is O(n log n).

2. Space Complexity:

   • Merge sort requires additional space to hold the temporary arrays during the merging process. This space is proportional to the size of the input array, leading to a space complexity of O(n).

Therefore, the appropriate answer would be:

• Time Complexity: O(n log n)
• Space Complexity: O(n)