若问题P的输入长度为 n,求解问题P 的算法 A 在图灵机模型下的时间复杂性为T(n),那么在对数耗费标准下,算法 A 在 RAM 模型下的时间复杂性为O(T^2(n))
证明:在对数耗费标准下,RAM程序模拟图灵机时所处理的最大程序不超过T(n),而RAM 程序在处理大小为 n 的整数时,时间耗费为log n ,因此,RAM模拟时间复杂性为T(n)的图灵机的一个计算步骤的对数耗费为O(T(n)),从而,模拟图灵机的整个 RAM程序的对数耗费为O(Tn logTn),因为任何该函数是属于O(T^2(n))的,所以定理得证。