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


  • -5
    C
    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?


  • 0
    O

    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.


  • 3
    B

    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.


Log in to reply
 

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