My O(n) solution runs faster than O(logn) solution over the test cases

  • 0

    The O(n) solution is simply go through the array and find the minimum number (if a[i] is smaller than a[i-1] then directly return a[i]). The O(logn) solution uses binary search idea as described at length in other threads. I guess there's no super long test case, so both solutions were accepted, and ironically, the O(logn) solution took longer than O(n) one (40 ms vs. 28ms).

  • -12

    If we have a target, using binary search should faster. But for this problem, we only find out the smallest, there is no need to do binary search.

  • 0

    The O(n) solution in the problem need 1 comparison every times during iterator and the size of iterator is less than n/2 on average. But in binary search, the routine may need more calculation in assignments, comparisons and operations in every times of iterator. Hence when your test dataset is too small or you are not so lucky, these calculations will dominant your runtime, get an even larger calculation in O(lgn) solution.

Log in to reply

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