You are given a bit-array $A[1 \ldots n]$ (i.e., $A[i] \in\{0,1\}$ for each $i$ ) and told that this is a "$0$ -to-$1$” bit-array. This means that for some (unknown) index $1 \leq j<n, A[1], \ldots, A[j]$ are all $0$ 's and $A[j+1], \ldots, A[n]$ are all $1$ 's. The index $j$ for such an array is called the transition index. We design a divide and conquer algorithm for finding the transition index for a given $0$ -to- $1$ bit-array. The input to the algorithm is an array $A$ and the size $n$ of the array $A$. What will be the worst case time complexity of best divide and conquer algorithm?
- $\Theta(\log n)$
- $\Theta(n \log n)$
- $\Theta(n)$
- $\Theta\left(n^{2}\right)$
