Resolva a recorrência

12

Como posso resolver a seguinte relação de recorrência?

f(n)=f(n1)+f(nlogn)
bolinho de massa mobius
fonte
5
O que você ganha se tentar ? Parece que você obterá um limite inferior de 2 Ω ( n / log n ) . f(n)=2f(nlogn)2Ω(n/logn)
Chandra Chekuri
2
@ChandraChekuri Oh, isso é ótimo! E existe um limite superior de : usamos o log de recorrência n vezes e obtemos que f ( n ) ( 1 + log n ) f ( n - log n ) . Então aplicamos esse n / log n vezes e obtemos f ( n ) ( 1 + log n2O(nloglogn/logn)lognf(n)(1+logn)f(nlogn)n/logn . Portanto, a diferença entre o limite superior e o limite inferior é apenas log log n no expoente. Isso é realmente suficiente para meus propósitos, mas deixarei a pergunta em aberto caso alguém queira e consiga fechar a lacuna. Muito obrigado, Chandra! f(n)(1+logn)n/logn=2O(nloglogn/logn)loglogn
mobius dumpling
4
Bem, o mesmo truque fornece , então f ( n ) = 2 Θ ( n log log n / log n ) . f(n)(logn)f(n2logn)f(n)=2Θ(nloglogn/logn)
Emil Jeřábek 3.0

Respostas:

14

f(n)=2Θ(nloglogn/logn) .

logn

f(n)=2f(nlogn)+f(nlogn1)++f(n2logn)lognf(nlogn) .
n/logn2Ω(nloglogn/logn)

logn

f(n)(logn+1)f(nlogn) .
n/logn2O(nloglogn/logn)
bolinho de massa mobius
fonte