The recent discovery of the following fragment of uncommented procedural C code in the Sunlab has caused a big scandal.
foo(int a[],int l,int r,int k)
{ int i;
i = partition(a,l,r);
if (i == k) return a[k];
else if (i < k) return foo(a,i+1,r,k);
else return foo(a,l,i-1,k); }
Since the author of the code is still hiding, we will have to decipher it. The TAs have already determined that function partition(int a[],int l,int r) works as follows: let v=a[r]; partition rearranges the subarray a[l] through a[r] such that the elements equal to v precede those greater than v and follow those smaller than v,
Class and returns an index i such that a[i]=v. Thus, partition works in the same manner as the function Partition of Quicksort discussed in class, returning the position of the partitioning element v in the rearranged subarray a[l...r]. Let a be an array of size N of integers, and 1 k N.
(a) What will foo(a,1,N,k) return?
(b) What is the worst-case time complexity of foo(a,1,N,k), and for which inputs does it occur?
(c) Can the running time of foo(a,1,N,k) be improved? If so, how? If not, why?