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?
