Временная сложность разделяй и властвуй

Question

У меня есть теорема Master для нахождения сложности, но проблема Master теорема говорит

Для повторения формы

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1 

Существуют следующие три случая: /****************** logba означает журнал А с Ь в качестве основания **************/

1. If f(n) = Θ(n^c) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(n^c) where c = Logba then T(n) = Θ(ncLog n)

3. If f(n) = Θ(n^c) where c > Logba then T(n) = Θ(f(n))

Теперь моя проблема

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

Мое решение c = 2 и logba = log из 2 с 1 в base = infinity Таким образом, в этом случае падает и какова сложность

Answer 1

В вашем случае b=2 и a=1 так Log_b(a) является log of 1 in base 2 и не log of 2 in base 1.

См:

T(n) = aT(n/b) + f(n) 
T(n) = T(n/2) + n^2 

Как Log_b(a) = Log_2(1) = 0, вы упадете в случае .