Tenho algumas dúvidas com a definição de funções polinomiais e exponenciais pedida pelo exercício 7. Podemos (devemos?) usar análise assintótica nessa definição?
Por exemplo, 'n^0.1', 'lg n' e '10n² + 3n' são todas funções polinomiais? (acho que fica inconsistente dizer que lg n é uma função polinomial sem que n² seja uma função exponencial - o que não é verdade pelo enunciado do ex. 7d)
Existem jeitos diferentes de definir que entram em conflito nos casos acima (mas que ainda assim funcionam para responder o item c do exercício)
Estou quase convencido que só o último exemplo (10n² + 3n) é polinomial, mas conversei com alguns colegas e a maior parte parece achar que todos são.
Da mesma forma, '3^{n²}', '5^{n lg n}', 'n^n', 'n!' e '2^{n^n}' são funções exponenciais?
A maior parte das pessoas pra quem perguntei respondeu que todas as acima são exponenciais (e eu estava convencido de que pelo menos as duas primeiras eram), mas como o objetivo do exercício parece ser mostrar que n^{lg n} não é nem polinomial nem exponencial, acho que não é tão simples :p
Eu acho (sempre nos achismos!) que o objetivo do exercício não é mostrar que nlgn não é polinomial nem exponencial, mas sim mostrar que para qualquer função polinomial existe um ponto a partir do qual nlgn a ultrapassa para sempre e também que qualquer função exponencial ultrapassa nlgn para sempre a partir de algum ponto.
Nesse sentido, acho que na definição de função polinomial e exponencial deve-se utilizar algo que dê uma uma cara para essas funções, e em seguida deve-se mostrar através de análise assintótica as coisas que eu falei no parágrado acima.
Será?
Nesse sentido, acho que na definição de função polinomial e exponencial deve-se utilizar algo que dê uma uma cara para essas funções, e em seguida deve-se mostrar através de análise assintótica as coisas que eu falei no parágrado acima.
Será?
Eu acho que existem duas noções misturadas no termo "função poliminomial". Uma seria uma função definida por um polinômio e outra seria uma função limitada superiormente por um polinômio. Pelo enunciado do exercício me parece mais adequado usar a primeira, apesar de que a segunda é a mais usual.
Concordo, mesmo porque senão a pergunta do ítem d viraria:
"Mostre que não existe função limitada superiormente por uma função exponencial que limite inferiormente nlgn."
"Mostre que não existe função limitada superiormente por uma função exponencial que limite inferiormente nlgn."