Big-O prova de uma relação de recorrência?

8

Essa pergunta é bastante específica na maneira de executar as etapas para resolver o problema.

Dado prove que .T(n)=2T(2n/3)+O(n)T(n)=O(n2)

Portanto, as etapas foram as seguintes. Queremos provar que .T(n)cn2

T(n)=2T(2n/3)+O(n)2c(2n/3)2+an(8/9)(cn2)+an
e meu professor continuou:

T(n)cn2+(an(1/9)cn2),
que sai para:

T(n)cn2 for any c>=9a.

Minha pergunta é: como eles conseguiram mudar de 9/9 para 1/9 enquanto introduziam um novo termo? Isso é permitido? Ela nunca explicou, isso foi apenas em suas soluções.

D. Johnson
fonte
2
Não vejo um novo termo introduzido? Temos que simplifica para como na linha anterior. Portanto, as duas linhas são realmente iguais. Talvez você esteja perguntando por que alguém pode querer fazer isso? cn2+an(1/9)cn2(8/9)cn2+an
user340082710
Também estou assumindo que a linha final deve ler em vez de . cn2ck2
user340082710
@ZacharyFrenette Ah, você está certo. Nesse caso, eu não tinha certeza de como ela fez a simplificação. Por que alguém escolheria separar os termos dessa maneira? existem várias maneiras de dividir (8/9). Eu acho que sei por que alguém iria querer fazer isso, para cancelar extra ? Caso contrário, a desigualdade não se manterá. Também obrigado por apontar o erro de digitação, irá corrigir. se você quiser comentar como resposta, posso aceitá-lo. an
D. Johnson

Respostas:

12

Como você disse, a razão para dividir o termo em duas partes é ser capaz de cancelar a prazo. Se formos diretamente de , então ficamos presos como não podemos fazer nada com o prazo. Dividindo-o da maneira descrita, isso permite que o seja maior que quando , o que fornece o resultado desejado desde que para esses valores de .an(8/9)cn2+ancn2+anan(1/9)cn2anc9aan(1/9)cn20c

user340082710
fonte