Метод замещения

Question

Я просто хотел проверить некоторые вещи, я сделал следующие шаги справа?

T(n) = 3T(n/3) + n : Theta(nlogn) 

O(nlogn) 

T(k) = cklog(k) k<n 

T(n/4) = c(n/3)log(n/3) 
     = c(n/3)[logn - log3] 
     = c(n/3)logn - c(n/3)log3  

T(n) = cnlogn-cnlog3 + n 

     <= cnlogn -cn + n 
     <= cnlogn -dn **[STEP A]** 
     <= cnlogn if c >= d 

Omega(nlogn) 
    >= cnlogn -cn + n 
    >= cnlogn -dn **[STEP A]** 
    >= cnlogn if 0 < c <= d 

У меня возникли проблемы с шагом, что я оказался в моих диапазонах с был:

с> = 1 для верхней границы < гр = 1 для нижней границы

Есть ли специальная причина, по которой вы бы объединили cn + n. Я могу видеть логику этого, но нужно ли делать этот шаг? Потому что тогда я могу сделать это для как любой случай ... который немного странно ..

Answer 1

Вы еще были правы до:

T(n) = cnlogn-cnlog3 + n 
    >= cnlogn -cn + n 

для Ω(nlogn)

, так как это имеет место только для с < = 0, которое противоречит нашему предположению, что с> = 0.

Один из способов исправить второе доказательство может быть:

T(n) = cnlogn - cnlog3 + n 
    = cnlogn - n(clog3 - 1) 
    <= cnlogn when c >= 1/log3 

Следовательно: T(n) = Ω(nlogn).

В общем, значения нижней границы и верхней границы не имеют большого значения. Цель состоит в том, чтобы найти две константы c1 и c2 таким образом, что:

c1*n*logn <= T(n) <= c2*n*logn ForAll n >= some n0.