Non duplicate element

Question

There is a sorted array which is of very large size. In those elements every element are repeated more than once except one element. How much time it will take to find that element?

• O(1)

• O(n)

• O(nlogn)

• O(logn)

I think its less than O(log n) (divide n conquer) but solution is O(n) 

Answer 1

Answer will be O(n) by divide and conquer also...

f(n)

{

O(1); //checking with center element

f(n/2); //for left half of array

f(n/2); //for right half of array.

}