Изменения

Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно раскрыть квантор для значения подставить в неравенство с квантором значение <tex>\sigma_n</tex>: и получить <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.