Pergunta assintótica

7

É n!2!4!8!(n/2)!=O(4n)?

Estou realmente paralisado e acredito que é verdade, mas não sei como provar.

Qualquer ajuda seria apreciada!

Dudi Frid
fonte
11
O que você tentou provar isso? Você já tentou usar a definição de grande O ou limites?
ryan
2
o denominador não é claro. é isso2!4!6!...? é isso2!4!8!16!...?
Lox
Tnx, eu editei a minha pergunta
Dudi Frid
Então parece que haverá n-2termos no denominador. Você pode emparelhar cada um desses termos com um termo no numerador que seja maior ou igual a ele? Por exemplo, o últimon/2 termos em (n/2)! iria emparelhar com o último n/2 termos em n!no numerador e cancele. Tente isso com o denominador inteiro.
ryan
Você poderia elaborar sua resposta? E você prova ou desaprova isso?
Dudi Frid

Respostas:

18

Temos Usando a aproximação de Stirling, podemos obter assintóticos mais refinados, mas deixamos isso para o leitor interessado.

n!(n/2)!(n/4)!2!=n!(n/2)!(n/2)!(n/2)!(n/4)!(n/4)!4!2!2!2!1!1!=(nn/2)(n/2n/4)(42)(21)2n2n/22422=2n+n/2++2+1<22n=4n.

Yuval Filmus
fonte
Como provar ? E se não for uma potência de ? n2+n4+...+2+1<nn2
Miniparser 01/09/19
Então, como é ? n+n2+n4+...+2+1<n+n=2n
miniparser 02/09/19
Meu comentário anterior estava errado. Temos . n+n/2+n/4++1=n(1+1/2+1/4++1/n)ni=02i=2n
Yuval Filmus
A OP implicitamente assume que é uma potência de 2.n
Yuval Filmus