Método da substituição (resolvendo recorrências)

Tá bom então uma vez que a gente tem uma recorrência né que no nosso caso vai tá escrevendo Por exemplo o tempo de execução de um algoritmo a gente precisar resolver né encontrar uma fórmula fechada para ela e uma das formas de fazer isso usando esse método aqui da substituição lá então a ideia de cimento do é provar algo por indução ainda eu vou provar por indução que a minha recorrência de higiene é limitada inferiormente ou Experimente os dois tá por alguma função ele ele é um quadrado é blog em alguma coisa do tipo certo

então quer dizer a gente já precisa saber quem é essa FG né que a gente já precisa ter um chute inicial de quem seria e referências limitantes inferior ou superior como fazer isso né Hum então pode ser que com o tempo você começa a olhar para uma recorrência e tem uma intuição de qual seria o resultado dela e você junta isso e tenta provar que isso é de fato ver o ou você pode usar uns outros métodos que que existem tá então é possível sim Sempre tem um chute inicial já vou deixar aqui de aviso

algo que eu vou comentar mais vezes depois que eu como eu estou me propondo a provar ao por indução eu quero levar uma expressão para opção eu tenho que provar exatamente aquilo que eu prometi tá então por exemplo eu queria provar que seja é menor ou igual a FDN então não passo da edição eu vou precisar provar isso daí eu não posso provar que ter DNA menor igual a 2 vezes FDN ou fgn mais 10 tá conforme gente faz discutindo acho que isso aqui vai ficar um pouco mais claro mas lembre-se sempre disso nosso primeiro

exemplo aqui eu peguei a recorrência do nerd sorte certo então uma recorrência independente da gente saber qual é o algoritmo que que deu ela para gente a gente sempre consegue olhar praia e mais ou menos saber o que que seu organismo faz tá então quê que isso que estão dizendo que o tempo o ritmo que executam na entrada de tamanho M é igual ao tempo de duas chamadas recursivas e entradas de tamanho M sobre dois e feito ao além dessa chamadas recursivas os em formato alguma coisa assim que leva até com ele certo e as

vocês lembram Na verdade eu escrevi lá no ter sorte certa DN né porque eu não que a gente que eu tinha conseguido dizer sobre o tempo do combina certo mas veja o que que é teto gênero é o quê que significa isso daqui significa que aqui eu gostaria de colocar uma expressão que é limitada inferiormente por n e superiormente também por Elle tá então essa função para todos os efeitos ela se comporta como uma função e tá e deixar só ele aqui facilita muito para gente as contas não está errado se você quiser colocar aqui

uma constante desse Gene para deixar mais mais parecido né com água é mas facilita muito mais e não fez diferença nenhuma Se você sumir com esse deixar aqui só m certo mesma coisa que aqui não tá escrito Qual é o tempo do caso-base mas quando não tá gente sempre vai sumir aqui por causa base até de um igual a um certo onde eu esqueci na verdade seria um teto de um aqui também né pelo menos motivos estão substituindo-os se trata de um por um E aí meu chute para essa recorrência que é que ela é

o zão DN tá ela é limitado valor de pedir n é limitado superiormente porém o quadrado deve ser uma constante desenho quadrado por que que eu escutei isso porque o estejam sóis por exemplo é uma linha um quadrado e aí eu apresentei uma Episódio falei que ele pode ser melhor então não vai passar de cereal quadrado eu fiquei esse aqui vale é válido não como um bom Chute Inicial Então mas como que a gente prova que algo é o adiante ao quadrado tô mostrando que existem as constantes cm0 natais que valeria que ter menor igual

a servir ser enquadrado para todo ela informar de quem certo Então essa é uma forma de provar agora nem o que esquece que você tá falando de notação assintótica porque eu quero provar essa expressão certo eu quero provar Exatamente isso daqui por indução tá eu ainda não sei quem é seu gente vai descobrir quem é o seu durante a a prova Ok mas é não são mais totalmente relacionado com o notação assintótica Então como toda prova por indução e a gente começa no caso base né causa do Águia aqui é a valor de n aí

menor possível que a gente consiga resolver na mão certo eu colocar então aí igual porque e agora eu quero provar essa expressão para ele igual um certo então a gente sabe que é ter de um é um e eu quero relacionar isso como que se eles um o quadrado né esse eles vão ao quadrado é igual a ser tá então para essa expressão ser verdade no caso base é de um tem que ser menor ou igual a você que o caso base Vale se ser o maior igual a um né E aí passado caso base

a gente quer mostrar né que ter dinheiro e Menor igual às vezes não quadrado para um ele é maior do que um certo que se n fosse igualmente já teria mostrado então podemos assumir aqui que está falando de um em maior do que um e para provar isso então a gente isso põe a hipótese né que dedicar para qualquer caminho enorme Kenny é menor igual quadrado a ser vezes cal quadrados é só agora eu quero mostrar o em cima de tarde ele o que que eu sei sobre o tdn eu sei o definição série mas

logo a definição já me apareceu aqui ó um objeto né Eu tô tentando desse objeto dessa concorrência o objeto menor né entendi ele sobre dois é enorme QN em se tratando de um ano aqui é o maior do que uma estão certamente resolvido esse menor que é então nisso aqui eu posso usar hipótese Então isso é sempre muito importante né para usar a hipótese a gente tem que argumentar primeiro que a gente tá falando da mesma objeto então eu ainda tô falando de ter de alguma coisa isso isso vai veio direto aqui mas eu tenho

que aumentar ou diminuir o tamanho da coisa que eu só tinha M eu tenho que mostrar que o que eu tenho agora é menor é ele sobre dois é menor do que ele sempre que ela informa maior do que um né se ele fosse 0 sobre a valer então a gente tem que tomar esse cuidado Sim sempre lembrando que tomar esse cuidado tá eu vou hipótese gente pode assumir que terreno sobre dois é menor ou igual a cê Presidente sobre ganham quadrado e bom isso aqui é igual a servissem ao quadrado sobre quatro certo Ah

tá agora que eu tenho essa informação eu vou substituir isso muito Eu sei né Na definição ali Ok então vale que tem DN que é igual é isso vai ser menor ou igual a essa expressão particularmente porque tem que eu descobri dois e menor ou igual a essa expressão né tenham quadrado sobre pato e aí é reescrevendo aqui dois sobre quatro vira meio né então a gente tem senha e ao quadrado sobre 2 mais é ó e aqui tá o motivo pelo qual eu fiquei falando meio que esquece que eu tô falando de lotação eu

a gente tá sempre fã de natação tá só que a gente não pode comprar um dia um negócio aqui você pararia poderia parar sua prova aqui né porque que surgiu um ele é um quadrado né mas ele só que isso claramente áudio ele é o quadrado então provei que ela tem ao contrário não né porque eu mostrava exatamente explicitamente querendo provar que era hora de um quadrado eu queria provar que essa expressão vale porque ela fica no modo de acordar tá então é é um pouquinho diferente eu quero provar essa expressão e eu não tô

com só CDN ao quadrado você vê desenhar um quadrado aqui esse é o problema tá se se for verdade que esse negócio é menor ou igual a ser vezes em o quadrado se essa parte aqui foi verdade Aí sim a prova Acabou lá então é importante perceber isso né eu me propus a provar essa expressão prata aqui saindo umas alguém ao quadrado então é por isso que eu meio que tentei que falar esquece por enquanto na notação assintótica mas é nesse sentido Tá bom mas então será que isso aqui é verdade porque tu tá impressão

de verdade porque veja eu quero isso aqui é metade do CM ao quadrado né então e ele é menor do que ele é um quadrado Então realmente na impressão que dependendo dos e eu posso isso que pode ser verdade certa e isso de fato a verdade se a gente manipular essa expressão um pouquinho a gente vai verificar que valores para quais valores de ser que ela bate então isso aqui é verdade se essa expressão que for verdadeira né se eu vou manipulada ela passei sem sobre sem um pedaço de 2 aparecer na direita a dividir

tudo por n ficou só isso né então eu descobri que basta que seja maior ou igual a 2 sobre ele para que ela ser verdade será que eu consigo encontrar uma constante sempre vai ser maior do que 2 sobre ele para qualquer n maior do que um né Veja essa 2 sobre ele quando ele vale um ela vale dois quando ele vale dois tava valendo quando ele vai de três ela vai de dois terços Então ela tá diminuindo né de fato 2 sobre ele tem de Eusébio né mas ela começa a lindo dois certo então

ela ela só assume valores de dois entre 20 né então para qualquer valor de ser que eu pegar maior do que isso mas é no próprio 22 vezes sempre maior do que essa expressão três vezes sempre maior do que se esqueçam perguntou querendo né então é possível se encontrar um cê de pets faça isso bom então né observando que é a expressão 2 sobre ele vai ser sempre menor do que 2 sempre que o n for maior que 1 basta que se sejam valor maior do que 2 para que isso aqui vaia e juntando esse

fato que eu preciso de um ser maior ou igual a 2 aqui embaixo e um ser maior vão lá no caso base então é bem fácil escolher um ser que vai nenhum dos lugares aqui então vai valer para todo n maior é igual a um então aqui a gente provou que elas vão DNA ao quadrado tomando por exemplo a constante c = sei lá vou pegar o valor assim que poderia ter pego Dois Três Quatro qualquer coisa O perigoso porque eu consegui provar né que vai para todo o valor de n e além acima de

um no contato caso base qualquer outro valor maior tá na está no Passo agora eu queria que vocês observar-se uma coisa é eu quis provar por indução essa expressão e ela me deu que ela me dá diretamente né então que teja é usar um dinheiro em um quadrado É mas eu não precisava mas tem escolhido exatamente essa expressão por exemplo eu poderia ter escondido essa expressão aqui mas é por exemplo né o mais alguma outra constante de exemplo e eu poderia ser aprovado aqui por indução que esteja em menor igual a isso sem ao quadrado

com as DN tá então é a gente teria que mudar aqui tá não é exatamente essa prova tá eu teria que inserir aqui um de cá por exemplo e mudar várias coisas mas eu poderia tentar provar por indução essa expressão agora certo e isso ainda me garantir ia que tem DNA elas vão ganhar o quadrado né porque porque essa expressão que isso é usando implantar isso é limitado superiormente por em um panela menor do que tenha um quadrado mais deem um quadrado que é ser mais de ele é o quadrado então ainda assim estaria provando

ação de enquadrar e briga uma falando isso porque vai ter casos que a gente vai ter que fazer isso vai de caso e que a gente vai se vai achar vai tentar provar isso não vai dar Vai trabalhar que eu vi É mas o próximo que eu vou dar já vai acontecer isso mas o nosso chute ainda estava certo e a gente precisa na verdade aí eu está a nossa hipótese então é o que vai acontecer nesse caso tá aí agora a gente tem essa sequência que eu não sei igual algoritmo ela se refere mais

lembra ela sempre diz algo para gente diz sobre seu bonito então o tempo que leva para executar uma Instância de tamanho n é no máximo o tempo de três chamadas recursivas é sobre Instância de tamanho n sobre 3 Ah e ainda tem um tempo extra para fazer algumas coisas que nesse caso aqui é um tempo constante E aí meu chute aqui é essa recorrência é o zão The L ta antes de eu continuar eu queria dizer uma coisa que vejo informações essa recorrência eu juro pra temer eu só estou dando um limitante superior né só

tô dizendo que ela é menor é igual alguma coisa então eu só vou conseguir realmente chutar um limitante superior exame alguma coisa é diferente do do exemplo anterior aqui eu eu chutei longe não quadrado mas a gente vai Nossa eu vou mostrar para vocês exemplos usando o ômega aqui no espaço tá então porque aqui eu sei o que que vai a recorrência na igualdade A então aqui a gente consegue dar limitante Justo quando a própria pedi ele é só definida em termos de um limitante superior eu só vou conseguir continuar dando limitantes superiores a ela

tá então vamos lá nosso tchau e janelas onde n então temporariamente Esquece isso um pouco o que eu quero provar ela alguma coisa desse tipo né porque se eu provar essa expressão se eu for mais que isso vale então eu estarei problema não que então vamos tentar provar que cê DNA menor igual às vezes são no caso base normal né n = 1 a gente sabe que ter de um é um eu não foi dado então o assumir ele e ser rezene vai ser é o caso base Vale se você for maior igual a um

certo então basta que a gente escolheu ser apropriada E aí eu que a gente quer mostrar que esteja em melhor igual a CN para qualquer n maior do que um né É É para provar isso eu vou assumir algo Extra isso vale esquecer de cai menor igual a se dedicar para qualquer cá menor do que é ele tem um né que é o caso base é então vou partir da definição eu sei que tem de em menor igual a 3cm sobre três mais um e a gente tenha nenhum objeto menor né tem que ter gente

sobre três aqui e ele sobre três é menor do que é quando ele é maior do que um é justamente ficar sem estar está um bocado em que nenhuma aquilo que a gente pode usar a hipótese em cima desse trechinho aqui ok então por definição de gene menor ou igual a 3 cm sobre três mais um e por hipótese de Regiane sobre três e melhor igual a certeza de 13 EA esse três vai cortar aqui né vai sobrar só senha ele mais um Oi e aí não acabou né porque a gente quer mostrar que ter

DNA menor igual a CNN e não melhor igual sem animais 1 Oi e aí mesma coisa que aconteceu antes né Será que a gente não consegue encontrar um cê para o qual ser mais um seria menor ou igual a Siri que não né realmente não tem jeito não não tem nem o que tentar manipular aqui para para ver que isso aqui é falso O problema é que esse chute que a gente deu de que a impressão que a gente tinha que ter Generosa Jenny é verdadeiro é mas é mas na hora de provar que falhou

tem esse pequeno problema aqui com o método de substituição que que é o fato de se você falou no passo e mostrar onde você queria não vai necessariamente significar que o que você queria mostrar tava errado eas caso aqui tá a gente quer mostrar que é onde ela está certo agora como eu resolvi mostrar isso que não fosse não me ajudou tá então a gente não vai desistir da ideia de ser um gênio por enquanto eu só vou mostrar esse de um outro jeito desse jeito vai ser adicionando uma constante aqui e na demonstração tá

então eu vou tentar provar por indução agora essa expressão que esteja em melhor igual às vezes animais de onde tanto você quanto de são constantes E aí eu vou ver se isso me ajuda na prova porque porque se eu conseguir mostrar isso como essa expressão é usar onde ele aí eu também vou está conseguindo mostrar o meu objetivo aqui que era uma zumbi ele para terça a questão é que agora na prova por indução esse de vai ficar aparecendo lá então as coisas que começa a iguais né no caso base igual a um ter de

um ainda é um então agora a gente tem que ser vezes vão mas de né esse negócio vai ter que ser isso a ser mais dê certo bom então o caso mais vai valer se ser mais de for maior ou igual a um quentão Guarda essa informação também de novo e agora que a gente quer mostrar aqui tem dinheiro e menor ou igual a 100 animais Z né então tem que ficar igualzinho a expressão lá em cima minha hipótese também vai ser de que ter carne no igual a secar mais de para tudo o que

a menor que n a e agora aqui sim vai fazer diferença né então a gente tem continua sendo verdade que tem a menor igual é isso nessa definição da recorrência não tem jeito ele ele sobre três continua sendo menor do que 3 agora na hora de substituir ali que a gente tem que tomar cuidado então aqui é por definição né da expressão e agora vou substituir esse ter gênio sobre três aqui vai ser menor ou igual a si Rezende sobre três mais dê certo vem aqui olha a hipótese troca o capotreno sobre três E aí

vó mas não continuar existindo ali fora né O que que a gente tem agora três se multiplica isso daqui vai virar 3cn né eu sei se multiplica o de e mais um Agora sim isso aqui tem chance de ser menor do que cm né porque basta que 3D Mas ou seja menor ou igual a zero e aí essa expressão toda que vai e aí o que eu queria provar vale e isso parece ser verdade o meu deu foi um número pequeno né ele negativo inclusive e inveja aqui então essa última expressão que Fabi sempre que

é trem demais um for menor ou igual a 0 era o que é verdade sempre que de for menor ou igual a um texto né então pegue essas pessoas aqui deixa o de de um lado sozinho você vai ver que ela de tem que ser menor igual a um terço para ela valer então eu vou pegar de valendo menos um terço mesmo ou é bom pode ser qualquer coisa menor do que isso né pra facilitar porque eu sei que ser mais ver tem que ser maior igual e eu vou tomar de valem a ilusão é

menor ou igual a menos um terço né aí agora o caso base tá me dando uma condição de que ser tem que ser maior ou igual a 2 certo se você for maior igual dois casos balé valer todo o resto vai valer aqui então e aí com você igual a dois da igual menos um a gente consegue mostrar aqui ter DNA menor igual a 2 n + 2 l -1 materiais né então se pedir n é menor ou igual a 2 n - 1 é isso aqui ele só que claramente a menor igual a 2

m então tem DNA pode é mesmo certo e a nossa chute estava certo desde o início