Доказательство наихудшего случая выполнения QuickSort

Question

Я пытаюсь выполнить асимптотический анализ следующей рекурсивной функции для эффективного способа вычисления числа.У меня возникают проблемы с определением уравнения повторения из-за наличия разных уравнений для случаев, когда мощность нечетна, а когда мощность четна.Я не уверен, как справиться с этой ситуацией.Я понимаю, что время выполнения - тэта (logn), поэтому любые советы о том, как поступить с этим результатом, будут приняты.

Recursive-Power(x, n):
if n == 1
   return x
if n is even
   y = Recursive-Power(x, n/2)
   return y*y
else
   y = Recursive-Power(x, (n-1)/2)
   return y*y*x

Answer 1

В любом случае выполняется условиеВлияние на результаты, уравнение неофициально записывается как:

T(n) = T(n/2) + Θ(1)

Вы правильно угадали асимптотическую оценкуРезультат может быть доказан с использованием метода подстановки или основной теоремы.Это оставлено для вас как упражнение.