educative.io

Educative

Find Minimum in Rotated Sorted Array

How the O(lg N) complexity in current problem ?
because you are filtering the list to new list means all elements are visited hence O(N),
next you use binary search to find index in O(lgN) time ,
so total complexity is O(N) + O(lgN) ~ O(N)

Hi @dragon

The algorithm doesn’t filter the given array into a new array. It just makes this decision using an if condition. It’s also evident from the code that it neither creates an extra array nor does it execute an extra loop. Therefore, the time complexity is O(log(N)).