Logo, para padronizar essa análise, em vez de considerar tempo real, utiliza-se o tamanho da entrada como referência. => Não sei se ficará claro para a turma "TAmanho da entrada". Talvez um exemplo caia bem nessa hora.
Uma aplicação é, em competições de programação, onde existe um limite de tempo para a execução de cada exercício, => trocar aplicação por => Uma situação comum encontrada, é, em, competições de programação, ... (Podem pensar que aplicação é um software)
necessidade de respostas rápidas não é apenas
uma questão de conforto para o usuário. Quanto maior for o tempo de processamento, maior será o consumo de energia, de água e o custo de infraestrutura, assim algoritmos eficientes não contribuem apenas para o desempenho dos sistemas, mas também para a sustentabilidade. (Adicionar) => Além disso, imagine que quando se detecta um desempenho insatisfatório, o desenvolvedor tem que reavaliar o código para melhorá-lo, envolvendo custo de pessoas e estrutura física e normalmente perdas financeiras.
Sugiro pegar um pequeno caso, tipo busca binária simplérrima e mostrar como fica a árvore de execução da entrada até a saída.
Espaço polinomial em Pspace: analogia da folha de papel - Contar um número muito grande. Meu espaço é o maior nro que quero encontrar pois posso escrever o 1o, nro, apagá-lo, escrever o 2o, e assim por diante até o último múmero.
Eu tiraria o Teorema de Savitch => vai complicar o entendimento L e NL também, talvez só citar.
EXplicar eficiência assintótica e limite superior assintótico
Representação e limites ?
Modelo de custo => ótimo Busca linear x Busca Binário => ok