Оценить сверху время работы (т.е. - Ответ на вопрос по основам программирования №1226201

Вопрос

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма:дано: x > 0, a > 1, ε > 0надо: вычислить loga x с точностью εвещ y, z, t;y := 0.0; z := x; t := 1.0;цикл пока |t| >= ε или z <= 1.0/a или z >= a| инвариант: ay * zt = x| если z >= a| | то| | z := z/a; y := y + t;| иначе если z <= 1.0/a| | то| | z := z*a; y := y - t;| иначе| | z := z*z; t := t/2.0;| конец есликонец циклаответ := y;

• Время работы не больше, чем C·log2 [x+1], где C — некоторая константа, [x+1] — целая часть числа x+1 (т.е. время пропорционально количеству цифр в двоичной или десятичной записи целой части числа x).
• Время работы не больше, чем C·log2 [x+1]·log2 (1/ε), где C — некоторая константа, а квадратные скобки обозначают целую часть. Иначе говоря, время пропорционально количеству цифр в двоичной или десятичной записи целой части x, умноженному на требуемое количество значащих цифр в дробной части результата.
• Время работы не больше, чем C·log2 [x+1] + log2 (1/ε), где C — некоторая константа, а квадратные скобки обозначают целую часть. Иначе говоря, время пропорционально сумме количества цифр в двоичной или десятичной записи целой части x и требуемого количества значащих цифр в дробной части результата.

Ответ