You are given an histogram and want to identify the area of the largest rectangle that fits under the histogram.

There is a solution in linear time using a stack. There is also a divide-and-conquer solution that we describe here.

On range $[l, r]$:

• Find the minimum $m$
• One rectangle candidate is $m \times (r - l + 1)$
• Other rectangle candidates are recursively computed on the left and right of the minimum.

So the complexity overall verifies: $T(n) = 2T(\frac{n}2) + f(n)$ where $f(n)$ is the cost of finding the minimum over an interval of length $n$.

## Finding the minimum efficiently over a range

1. If $f(n) = O(n)$, master theorem says complexity is $T(n) = \Theta(n \log n)$.
2. If $f(n) = O(1)$, master theorem says complexity is $T(n) = \Theta(n)$.
3. If $f(n) = O(\log n)$, well master theorem can’t be used; we can use instead a generalization called the Akra-Bazzi theorem (1998) with $p = 1, g(x) = \log x$:
\begin{align} T(x) & = \Theta\left(x\left(1 + \int_1^x \frac{g(u)}{u^2} du\right)\right)\\ & = \Theta\left(x\left(1 + \left[- \frac{\log x + 1}{x} + 1\right]\right)\right)\\ & = \Theta(2x - \log(x)) & = O(x). \end{align}