A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the...

Transcribed Image Text:

A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the time complexity you listed above in Part A. Algorithm Quicksort (A, left, right) if (left right) pivot Point i left - 1 right + 1 do do [(left+right)/2] // note central pivot 1+1+1 while (i < A.size) and (A[i] A[pivot Point]) do jj-1 while (ji) and (A[j] 2 A[pivotPoint]) if (ij) then swap (A[i], Aljl) while (ij) if (i < pivot Point) then ji swap (A[pivot Point], A[j]) Quicksort (A, left, j-1) Quicksort (A, j+1, right) endif C. Show the steps followed by the Quicksort algorithm given above in pseudocode when sorting the list E,X,A,M,P,L,E,A,N,S,W,E,R. Draw one figure for each call to Quicksort. You may omit calls where left right. D. If we want a hash table that stores a set of strings, one possible hash function is the string's length, h(x) = x.length. Is this a good hash function? Explain your ancwor A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the time complexity you listed above in Part A. Algorithm Quicksort (A, left, right) if (left right) pivot Point i left - 1 right + 1 do do [(left+right)/2] // note central pivot 1+1+1 while (i < A.size) and (A[i] A[pivot Point]) do jj-1 while (ji) and (A[j] 2 A[pivotPoint]) if (ij) then swap (A[i], Aljl) while (ij) if (i < pivot Point) then ji swap (A[pivot Point], A[j]) Quicksort (A, left, j-1) Quicksort (A, j+1, right) endif C. Show the steps followed by the Quicksort algorithm given above in pseudocode when sorting the list E,X,A,M,P,L,E,A,N,S,W,E,R. Draw one figure for each call to Quicksort. You may omit calls where left right. D. If we want a hash table that stores a set of strings, one possible hash function is the string's length, h(x) = x.length. Is this a good hash function? Explain your ancwor

Answer rating: 100% (QA)

A The time complexity of Merge Sort is On log n where n is the number of elements in the array to be ... View the full answer