Find matrix local minimum - two analysis which seem to get contradictory runtimes

Question

Suppose you have an $n\times n$ matrix and you want to find a local minimum. To find it you scan the middle row and column and identify a minimum. If it is a local minimum, you're done; if not, you recursively search the sub-quadrant where the smaller value was found.

Now I can analyze the runtime in two different ways. In the first analysis, I can count up how many cells of the matrix the algorithm will use: $2n + n + n/2 + ... + 1$ in the worst case, which has growth $\Theta(n\lg n)$.

In the second analysis, I point out that recursively, $T(n)=T(n/2)+cn$. By the Master Theorem this has runtime $O(n)$.

I can't see any way to reconcile these two analyses.

Answer 1

In the first analysis note that,

$T(n) = 2n + n + \frac n 2 + \frac n 4 +... + \frac n {2^{\lg n}} \leq n (2+1+\frac 1 2 + \frac 1 4 +... ) \leq 4n =O(n) $