Researchers have developed a breakthrough algorithm for the "list labeling" or "bookshelf" problem that significantly improves upon 40+ years of stagnant progress. The new algorithm achieves a cost of log n × (log(log n))² per insertion, dramatically better than the previous best of log^1.5 n. This advance combines "laziness" from history-independent algorithms with proactive adversarial response through strategic randomization. The improvement brings the algorithm close to the theoretical lower bound of log n and could potentially challenge binary search trees as the dominant data structure for sorted data if further optimized for practical implementation.
Sort: