The pseudo / java code find only global minima and…
Himadri Sarkar - Mar 0, 2014
The pseudo / java code find only global minima and that too when no other local minima exist. I don’t think this problem can be solved in less than O(n)
Hi Himadri, thanks for the comment. But I think the code is intended to give us local minima, and as we are apply binary search logic, it is possible in O(log n). I have added edit note in the blog post as well :
We are not enumerating all the local minima in the array, but a single LM, which can be done in O(log n) time. The number of local minima can be n/2; you can’t enumerate them all in O(log n) time.
It also doesn’t guarantee whether we will get global minima or not. Consider the array {8,5,4,3,1,2,6,9}, the output will be 1, as it is only LM here, not because it is a global minima.
The method doesn’t guarantee any particular local minima. Consider the array : {8,5,4,3,6,4,5,1,2,6,4,5,9}. The LM outputted by the code will be 3, which is one of the LMs in the array. The LMs we had in array were 3,4,1,4. But the code returned 3, which is one of the LMs.
Please let me know if this makes sense?