O(Log N). This will happen when we are in the n-th iteration, and the position where the current element should be inserted is such that the binary search takes O(log N) steps.