T(n) = 4T(n/2) + n2 решение с использованием метода дерева повторений
При использовании основного метода решение этой рекуррентности T(n) = 4T(n/2) + n2 равно "n2*logbase2 N", но с использованием дерева рекуррентности; высота его дерева будет:
(№ листа)N=d^h ==> N=4^h ==> logbase4 N = h
и, наконец, T (n) = O (n^2*logbase4 N) будет его временем выполнения, но не "n^2*logbase2 N", как с помощью основного метода. Я прав?
[Обновление № 1]
Как я обнаружил, база журналов не имеет значения в случае анализа Big O. Тем самым, O(n^2*logbase4 N) может быть равно O(n^2*logbase2 N)Asymptotically