Why is O(logN) impossible?


  • 0
    E

    Here is a binary-search solution accepted by the online judge that is guaranteed to terminate after O(logN) iterations:

    class Solution {
    public:
        int findMin(vector<int> &num) {
            
            int firstVal = num[0];
    
            int beg = 0;
            int end = num.size() - 2;
            
            while(beg <= end)
            {
                int middle = (beg + end) / 2;
                if(num[middle] >= firstVal && num[middle+1] <= firstVal && num[middle] > num[middle+1])
                {
                    return num[middle+1];
                }
                else if(num[middle+1] >= num[middle] && num[middle] >= firstVal)
                {
                    beg = middle + 1;
                }
                else //if(num[middle] <= firstVal && num[middle + 1] <= firstVal)
                {
                    end = middle - 1;
                }
            }
        
            return firstVal;
            
        }
    };
    

    Is there any input (further than those provided by the judge) that this algorithm would fail to solve correctly?


  • 0
    M

    You will get O(logN) in average case. However, worst case time complexity is still O(N). That's because duplicates are allowed. What if all the values in input array are the same? Your algorithm will walk through all of them!


  • 0
    E

    [deleted comment]


  • 0
    E

    Actually, the question is only asking about finding the minimum and for that goal the above algorithm still always produces the correct answer in O(logN) time. It would not be able to find the exact position of rotation in O(logN) time, but it's definitely possible to find the minimum element in O(logN) time.


  • 0
    E

    If the entire array is the same, then my algorithm will still quit after logN steps and reports the value of the first item in the array, the range of [beg,end] halves every iteration.


  • 0
    M

    I see what you're saying. But, as you pointed out your algorithm won't be able to find correct minimum for the case when input array is something like: "2212222222".


  • 0
    E

    Yeah, I realize now. My code wouldn't be able to differentiate between 2212222222 vs 2222222122 and might produce the wrong answer. I wonder why the judge doesn't test on these corner cases..


Log in to reply
 

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