questão 9.3.1

[xth1]

Olá pessoal,
Alguem tentou fazer esta questão?
Nós (eu e o Pedro) fizemos uma argumentação de que o algoritmo não O(n) para grupos de 3 elementos usando o método da substituição.

[Carla Négri]

Eu fiz ela e provei para grupos de 7 elementos.
Não formalizei para grupos de 3, mas a recorrência nesse caso não é O(n) mesmo.. é Omega(n lg n) né?

--
Carla Négri Lintzmayer (@carlanegri)
Mestranda em Ciência da Computação pela Universidade Estadual de Campinas
Bacharel em Ciência da Computação pela Universidade Estadual de Maringá

"Política é para o presente, mas uma equação é para a eternidade." (Albert Einstein)

[xth1]

Eu não tentei fazer dessa forma, mas provar que é omega(nlogn) com certeza prova que não é O(n) :) .

[Greice]

Olá pessoal, estou com uma dúvida nesse exercicio, como eu chego a conclusão (provando) que não é O(n)? Eu consegui chegar na recorrencia, mas não consigo entender o porque não é linear, é só ver que a prova T(n) <= cn não dá certo?

Obrigada,

Greice

[xth1]

O método de substituição é suficiente para mostrar que um algoritmo possui uma complexidade, mas é suficiente para mostrar que um algoritmo não possui uma complexidade?