Нужна помощь в понимании основной теоремы в этом доказательстве

Question

Буду очень признателен, если кто-нибудь поможет мне с парой вопросов,

Для каждого из следующих определений рекурсивных функций используйте основную теорему, чтобы определить ее асимптотический порядок роста (т. Е. Big-Tetha). Если вы считаете, что основная теорема неприменима к определенному случаю, объясните, почему. Можете ли вы в некоторых случаях предоставить разумную верхнюю границу (например, Big-O) для времени выполнения? Обратите внимание, что все базовые случаи предполагаются постоянными.

(а) T (n) = T (n / 2) + 2 ^ n

(б) T (n) = 4T(n/2) +(n^1,5) - 1

(c) T (n) = T (n / 3) + 100

(d) T (n) = 125T (n / 5) + n ^ 3 / logn

(e) T (n) = 2T (n / 7) + log n + √n

Я только что прочитал кое-что в Интернете об этом, и мне не хватает понимания, чтобы ответить на этот вопрос. любая помощь будет высоко ценится, я пытаюсь подготовиться к тесту, и я не получаю ничего из этого!

Большое спасибо!

Answer 1

Все элементы, кроме (а), работают с теоремой Мастера. В случае (а) функция оплаты не является полиномом и, следовательно, основная теорема не применяется. Но это можно решить путем расширения:

T(n) = 2^n + T(n/2) 
     = 2^n + 2^(n/2) + T(n/4) 
     = 2^n + 2^(n/2) + 2^(n/4) + T(n/8)
     = ... 
     = O(2^n).

Результат ясен, интерпретируя повторение как суммы двоичных чисел: 1+10+100+10000+10000000 <= 2*10000000.