T(n) => wyznaczyć O(n) Nana: Czy to jest dobrze rozwiązane? Chodziło o wyznaczenie O(n). T(n)= 2 * T(n^1/3) + log₃n n = 3^k T(3^k) = 2*T(3^k/3) + log₃3^k T(3^k) = 2*T(3^k/3) + k T(3^k) = S(k) S(k) = 2 * T(k/3) + k a = 2, b = 3 f(k) = k => f(b) = b = 3 czyli: a < f(b) zatem: T(k) = O(k^alfa) => O(k¹) => O(log n)