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

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.

$$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)$$