Let $C$ be an array with length $n$ (assume the elements are cities with some properties). We have some properties sorted by importance. For example, 1.area, 2.population size, .... We use the following algorithm to find the best city according to sorted properties:

We choose the first property and examine each city. Then we delete half of the cities. (assume we can do this by $O(n)$ time.) Now we apply the second properties and again delete half of the remain cities. We continue this way until one city remains.

Can we say the running time is equal to $O(n)$ according to the recursive function $T(n)= T(n/2)+ O(n)$, and the master theorem or the running time is equal to $n \log(n)$ because we use binary search and in each iteration, we apply an operator in linear time?

which is correct and why another one is incorrect?

  • $\begingroup$ Where are you using binary search? $\endgroup$
    – gnasher729
    Oct 26, 2018 at 20:13

1 Answer 1


The $T(n)= 2 T(n/2)+O(n)$ is $\mathcal{O}(n \log(n))$

Your recursion $T(n)=T(n/2)+O(n)$ is $\mathcal{O}(n)$ by The 3rd case of The Master Theorem.

  • $\begingroup$ Does the recursion function $T(n)= T(n/2)+O(n)$ correct for the mentioned algorithm? $\endgroup$
    – A.R.S
    Oct 26, 2018 at 10:50
  • $\begingroup$ Yes, it is correct. put $cn$ instead of $\mathcal{O}(n)$ and see by recursion tree, actually vine(backbone). $\endgroup$
    – kelalaka
    Oct 26, 2018 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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