In sorted array of numbers binary search gives us comlexity of O(logN). How will the complexity change if we split array into 3 parts instead of 2 during search?


Same. You will get a running time only differing by constant factor ($\log_2 3=\frac{\ln 3}{\ln 2}$).

  • $\begingroup$ Can you explain? $\endgroup$ – TOP KEK May 28 '13 at 14:36
  • $\begingroup$ If you know how to prove it for binary search, you can easily write down the recurrence relation (it's basically the same idea, except that the size of the subinstance is not longer n/2). See also Ternary search on Wikipedia (or in any Algorithms book, I reckon). $\endgroup$ – Clement C. May 28 '13 at 15:55
  • $\begingroup$ Not exactly. The ternary search takes two comparisons per interval, at worse, so $2\log_3N=2\ln N/\ln3$ in total, vs. $\log_2N=\ln N/\ln2$. The ratio is about $\ln4/\ln3$, in favor of the binary search. $\endgroup$ – Yves Daoust Aug 6 '14 at 9:58

You can apply the master theorem directly using:

$$ T(n) = T\left( \frac{n}{3} \right) + O(1) $$

But you can also think intuitively reasoning that if you search on a portion of the array that is 1/3 every time, and you finish when the array portion is of length 1 you need $k$ steps to complete the algorithm, with $k$ computed as:

$$ \frac{n}{3^k} = 1 $$

Therefore $k = log_3 n$, and $O(\log_3 n)$ is the complexity of the algorithm.

The ternary search suggested by Clement C. solves a slightly different problem, where you actually search for a maximum or minimum and not for a specific, given, item. In that case your recursion goes on 2/3 of the array instead of 1/3. I remains true, in any case, that the result is different only by a multiplicative constant, because you can always change the base.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.