Как я могу развернуть рецидив: T(n)=2T((n+2)/3)

Question

Я пытаюсь решить эту проблему, но я не знаю, как ее раскрыть.

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

Могу ли я проигнорировать это "+2" и решить его, как это было 2T(n/3) + 1?

Это происходит из-за проблемы, которая использует V[a..b] массив и делает это возвращение:

return V(X) + f(V, a, Y) + f(V, Z, b)

куда Y является (2a+b)/3 and Z is (a+2b)/3

Так: ((b-a+3)/3) = ((n+2)/3)

Answer 1

Вроде, как бы, что-то вроде. Строгая версия этого трюка состоит в том, чтобы установить U(n) = T(n+1) и писать

U(n) = T(n+1)
     = 2T((n+1+2)/3) + 1
     = 2T(n/3 + 1) + 1
     = 2U(n/3) + 1.

Тогда решите для U (например, U(n) = O(n^log3(2))) и тогда вы сможете найти асимптотическое выражение для T того же порядка.