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

Вопрос

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:дано: основание a и показатель степени n >= 0надо: вычислить a в степени nвещ b, p; цел k;b := a; p := 1.0; k := n;цикл пока k > 0| инвариант: bk p = an| если k четное| | то| | k := k / 2;| | b := b * b;| | иначе| | k := k - 1;| | p := p * b;| конец есликонец циклаответ := p;

• Время работы не больше, чем C·n, где C — некоторая константа (т.е. время пропорционально числу n).
• Время работы не больше, чем C·log2 n, где C — некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи числа n).
• Время работы не больше, чем C·r, где C — некоторая константа, r — квадратный корень из числа n (т.е. время пропорционально квадратному корню из n).

Ответ