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.


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


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.