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.