# Tag Info

### $O(n \log n)$ Algorithm for first Train Problem

Hint 1: Your approach is good. The algorithm type you are looking for is called a "scan line" algorithm. The idea is that you move from left to right on your 2d model and at each ...
• 1,106
$O(\log n)$ is very fast. I think it is unlikely that you will find a faster algorithm to compute such a function. Wavelets, polynomials, data compression, and enumerating combinations/permutations ...
Let $k=\lg(n)+c$. $(1) = O(\lg(n)),$ $(2) = O(2^{\lg(n)+c}\lg(n))=O(n\log(n)).$