Is my solution really O(log(m+n))? (beats 80% C solutions)

• ``````double findMedianSortedArrays(int A[], int m, int B[], int n) {
int C[m+n];
int im=0;
int in=0;
while(im<m && in < n){
if(A[im]<=B[in]){
im++;
C[im+in-1] = A[im-1];
}else{
in++;
C[im+in-1] = B[in-1];
}
}
if(im<m){
for(im;im<m;im++){
C[im+in] = A[im];
}
}else if(in < n){
for(in;in<n;in++){
C[im+in] = B[in];
}
}
if((m+n)%2==0)
return ((float)C[(m+n)/2] + C[(m+n-1)/2])/2;
else
return C[(m+n)/2];
}
``````

worst case: O(m+n)
best case O(1)
but what is the overall complexity?

• I think this solution need a array C who has m+n elements and costs O(n+m) time complexity to be created. Therefore this one should be a O(m+n) solution.

• No, your solution is not O(log(m+n)) but O(m+n).

What you did is just a simple merge sort and then picked up the median element. The merge sort part always has a time complexity of O(m+n), so the overall complexity would be O(m+n).

On a side note, I believe the test cases are too small, so that some invalid solutions may complete sooner than valid ones even though they have a higher time complexity. To fully test the efficiency of such a algorithm, the input array should at least contain hundreds of thousands of elements, which I don't think the OJ's test cases have included.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.