Why isnt this Divide and Conquer AC solution faster than Binary Search?


  • 0
    S

    Isnt this using O(lgN) complexity?

    public int findPeakElementDNC(int[] nums, int lo, int hi ) {
        if ( lo < hi ) {
            int mid = (hi + lo)/2;
            int peakLower = findPeakElementDNC( nums, lo, mid );
            int peakHigher = findPeakElementDNC( nums, mid + 1, hi );
            if ( nums[ peakLower ] < nums[ peakHigher ] ) {
                return peakHigher;
            } else {
                return peakLower;
            }
        } else {
            return lo;
        }   
    }

  • 1
    J

    I had a similiar AC solution,

    public class Solution {
    int solve(int[] nums, int l, int r){
        int mid = l+(r-l)/2;
        
        if(l > r) return -1;
        
        if(mid == 0)
            if(nums[mid] > nums[mid+1]) return mid;
            else return solve(nums, mid+1, r);
        else if(mid == nums.length-1)
            if(nums[mid] > nums[mid-1]) return mid;
            else return solve(nums, l, mid-1);
        else if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;
        else return Math.max(solve(nums, l, mid-1), solve(nums, mid+1, r));
    }
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        else return solve(nums, 0, nums.length-1);    
    }
    

    }

    and I also had the same question. Once I thought about it more though I realized this is not an O(logN) solution but it is in fact an O(N) solution. For each of the logN splits we make 2 recursive calls which gives us O(2^(logN)) = O(N). I had to think about it because I was wondering the same thing while thinking about this problem so do correct me if I am wrong anybody.


  • 0
    S

    Yea your right, it is a O(N) solution. I remembered much later that such recursions complexity can be solved by the Master method. You can check the video explaining it here https://www.youtube.com/watch?v=pXED5yrNyMg. The solution is pretty much simple substitution into the formula after that.


Log in to reply
 

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