Usamos cookies para medir audiência e melhorar sua experiência. Você pode aceitar ou recusar a qualquer momento. Veja sobre o iMasters.
Olá pessoal, estou com uma grande dúvida em Complexidade de Algoritmos e gostaria de saber se alguém poderia me ajudar!! É URGENTE!!!!!
Estava estudando complexidade de algoritmos pelo livro Projeto de Algoritmos de Nivio Ziviane e fiquei em dúvida em uma afirmação em um dos exemplos do livro:
Suponha g(n) = n e f(n) = n^2. Sabemos pela definição acima que g(n) é O(n^2), pois para n >= 0, n <= n^2. Entretanto f(n) não é O(n). Suponha que existam
constantes c em tais que para todo n >= m, n^2 <= cn. Logo c >= n para qualquer n >= m, e não existe uma constante c que possa ser maior ou igual a n para
todo n.
Bom a dúvida é que não entendi porque g(n) é O(n), e f(n) não é O(n)?
Poderiam me explicar fazendo o favor de uma maneira que consiga entender, desde já agradeço pessoal!!!
Carregando comentários...