Timeline for What is meant by a meet-in-the-middle approach?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2023 at 11:52 | vote | accept | Manuel Bravi | ||
| Feb 2, 2023 at 15:50 | comment | added | Peter Taylor | @NoamD.Elkies, if the structure can be hashed then it might be possible to eliminate the sort and get to $O(N)$ time. | |
| Feb 2, 2023 at 15:25 | comment | added | Noam D. Elkies | NB it's not obvious that this is an improvement: instead of searching the $N^2$ leaves of a single tree, we seek a coincidence between the $N+N$ leaves of two trees, which might still seem to take time $N^2$ to find. The key is that sorting can be done in time $O(N \log N)$, and once each tree's leaves are sorted we can find a match in time only $O(N)$. Likewise for other applications of this trick. Note that this requires on the order of $N$ space; sometimes there are refinements that reduce the space cost while keeping the $O(N \log N)$ timing. | |
| Feb 2, 2023 at 15:01 | history | answered | Carlo Beenakker | CC BY-SA 4.0 |