Teorema del maestro con f (n) = log n

Question

Apr 01, 2013, 01:04 AM

big-o master-theorem divide-and-conquer algorithm

Teorema del maestro con f (n) = log n

Para el teorema del maestroT(n) = a*T(n/b) + f(n) Estoy usando 3 casos:

Sia*f(n/b) = c*f(n) por alguna constantec > 1 entoncesT(n) = (n^log(b) a)Sia*f(n/b) = f(n) entoncesT(n) = (f(n) log(b) n)Sia*f(n/b) = c*f(n) por alguna constantec < 1 entoncesT(n) = (f(n))

Pero cuandof(n) = log n on*log n, El valor dec es dependiente del valor de n. ¿Cómo resuelvo la función recursiva usando el teorema del maestro?