Assume A is an unsorted array of all positive integers in range 0 to n except for one integer. Time required to find this unknown integer is
(Assume n = 2k-1)
1
O (logn)
2
O (n) but not O (logn)
3
O(nlogn) but not O(n)
4
\(Q\left( {\sqrt n } \right)\)