Оценить сверху время работы (т.е. количествовыполнений тела - Ответ на вопрос по Прог №1247009

Вопрос

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма:double myLog(double x, double a, double eps) { // дано: x > 0, a > 1, eps > 0 // надо: вычислить log_a x с точностью eps double y = 0.0, z = x, t = 1.0; while ( fabs(t) > eps || x <= 1.0/a || z >= a ) { // Invariant: a^y * z^t == x if (z >= a) { z /= a; y += t; } else if (z <= 1.0/a) { z *= a; y -= t; } else { z *= z; t /= 2.0; } } return y;}

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

Ответ