1
$\begingroup$

I know that this problem is solvable in linear time with a merge but I want to get a sub-linear algorithm. What I came up is that, if a[k] < b[k] then the $k$th element can not be in the sub array a[0..k-1] or in b[k+1..n]. But I am not able to construct the recursive relation. What I came up is

find(i,A,B):
    k=i/2;
    if n=1:
       return min of a[0],b[0]
    else if A[k] < B[k]
       recursively compute find (k,A[k+1..n],B[0..k-1])
    else if A[k] > B[k] recursively compute find(k,A[0..k-1],B[k+1..n])

Can any one guide me possible flaws in this?

$\endgroup$
  • $\begingroup$ Why do you think that sublinear time is possible? Why do you think algorithm is wrong and/or too slow? $\endgroup$ – Raphael Mar 13 '15 at 10:07
  • $\begingroup$ I assume your arrays are sorted in increasing order (You should be explicit). When talking of complexity, it is also better to be explicit regarding the reference quantity, which here is k. Comparing a[k] and b[k] will not give you any relevant information. The one thing immediately clear is that a[i] and b[i] do not matter for any ik, since indexing begins at 0. $\endgroup$ – babou Mar 13 '15 at 10:41
  • $\begingroup$ @Raphael I think its possible to have sub linear time as this problem is similar to binary search in some way . $\endgroup$ – Susmita Ghosh Mar 13 '15 at 13:48
  • $\begingroup$ Yes arrays can be sorted in either way ,just that my assumption is array is sorted in increasing order ,the order change does not change the algorithm much ,just that the portion of array which we discard in each recursive call changes $\endgroup$ – Susmita Ghosh Mar 13 '15 at 13:51
  • $\begingroup$ why do u think that comparing a[k] and b[k] wont give any relevant information ,if array is sorted in increasing order ,then if k th element of A is less than K th element of B then can it be possible that the element of A[0] to A[k-1] to be greater than B[k] $\endgroup$ – Susmita Ghosh Mar 13 '15 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.