Consider the following recursive algorithm:
Unknown(A,i,j);
{
if A[i] > A[j] then exchange A[i] and A[j];
if i+1 >= j then return;
k = (j-i+1) / 3; //integer division
Unknown(A,i,j-k);
Unknown(A,i+k,j);
Unknown (A,i,j-k);
}
a) What does Unknown(A,1,n) do?
b) Prove that it indeed does what you have said in (a).
c) Give a recurrence for the worst-case time of Unknown(A,1,n) and solve it in big Theta.
Question
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
a) The given algorithm sorts the array 1..n, by taking first 2/3 of array, then last two 2/3 of the array and in the end first 2/3 again (this because of the value of k, which is about 1/3 of the array length)....
Return to homework library