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

• 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;
}
}``````

• 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.

• 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.

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