Во-первых, воздержитесь от использования ссылок, так как они могут прекратиться.
Вы могли бы легко ввести код на картинке, как я сделал ниже
def select_number(A, low, high):
if low == high:
return A[low]
mid = (low+high) // 2
if A[mid] < A[mid+1]:
return select_number(A, mid+1, high) #line 6
else:
return select_number(A, low, mid) #line 8
Пользователь звонит select_number(A, 0, len(A)-1).
Без использования основной теоремы мы можем видеть, что любой вызов select_number будет вызывать не более одного рекурсивного вызова, каждый раз уменьшая пространство ввода вдвое. Это похоже на бинарный поиск, поэтому ожидаемое время выполнения должно быть в log n.
Вы рассчитываете время выполнения строк 6 и 8 отдельно, тогда как они взаимоисключающие: если одна запускается, другая нет.
Так что это не 2T (n / 2), а просто T (n / 2), что является решением в D.