Skip to content
Advertisement

what’s the growth order of “find a peak” algorithm

hello i need to apply an algorithm similar to this but the problem is that i need the complexity to be O(logn). the complexity of the code below is said to be O(logn) but from what i understand a recursive method has the growth order of O(n). so the question is what is the growth order of the code below.

  public static int findPeak(int[] array, int start, int end) {
        int index = start + (end - start) / 2;
    
        if (index - 1 >= 0 && array[index] < array[index - 1]) {
            return findPeak(array, start, index - 1);
        } else if (index + 1 <= array.length - 1 && array[index] < array[index + 1]) {
            return findPeak(array, index + 1, end);
        } else {
            return array[index];
        }
    }

Advertisement

Answer

It should be O(logn). For simplicity (also an easy way to think) think of this as creating a binary tree. In each function call it divide the input array into two halves (creating nodes in a binary tree). So if the number of input are n then the binary tree has log(n) levels (one level -> one function call).

Also note that in one function call only one recursive call happen( either in if block or else block but not both). This might made you feel it like o(n) growth.

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement