Изменения

Так как размер списка <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, а количество блоков всего <tex>\lceil n/m \rceil</tex>. То общее количество присваиваний новых ключей элементам последовательности , также как и количество операций слияния списков, не больше <tex>2cm\cdot\dfrac{n}{m}=O(n)</tex>, где c — некоторая константа. Каждая операция с приоритетной очередью требует <tex>O(\log \log m)</tex> времени, так как элементы в <tex>B</tex> не больше <tex>2m</tex>. Докажем, что реализация данного алгоритма будет работать за время <tex>O(n \log \log m)</tex> для последовательности длины n.

Будем по порядку для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди <tex>B</tex> становится больше <tex>m_i</tex>, то условие <tex>m \geqslant k</tex> перестает выполняться, тогда останавливаем алгоритм, и переходим к следующему элементу значению <tex>m_{i+1}</tex>. Когда найдётся первое <tex>m_j:m_j\geqslant k</tex>, то алгоритм успешно завершится.

Таким образом, время работы запущенного алгоритма — <tex>O(n \log \log {m_i})</tex> для <tex>0\leqslant i < \leqslant j</tex>, потому что во время работы очередь <tex>B</tex> хранит не более <tex>m_i</tex> элементов, ключи которых не больше <tex>2m_i</tex>. Для значения <tex>m_j</tex> алгоритм успешно завершается, так как условие полной обработки последовательности <tex>m\geqslant k</tex> выполняется. Таким образом, время работы алгоритма для <tex>m_j</tex> также <tex>O(n\log \log {m_j})</tex>.

Общее время работы алгоритма по всем <tex>m_i</tex> — <tex>O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \log m_i)</tex>. 

ЗаметимОбратим внимание, что <tex>m_i < k^{\operatorname{log}k}</tex>, т.к. так как в противном случае <tex>m_{i-1} > k</tex>, что противоречит тому, что <tex>m_i</tex> — первый из тех, что которые больше <tex>k</tex>. Следовательно, <tex>\operatorname{log}\operatorname{log}m_i < 2\operatorname{log}\operatorname{log}k \</tex>.

Тогда алгоритм также работает за время <tex>O(n\operatorname{log}\operatorname{log}k)</tex>.