En Algoritmos y estructura de datos, ¿cómo puedo probar o refutar la siguiente ecuación: n * (2 ^ n) = O (n ^ n)?

Answer 1

Como Michael Levin mencionó, se deduce de la definición formal y puedes probarlo.

En términos de comprender intuitivamente por qué es así, considere primero que big-O es un límite superior; queremos saber si [math] n \ cdot 2 ^ n [/ math] está delimitado por [math] n ^ n [/ matemáticas]. Considere que [math] n ^ n [/ math] es más grande que [math] n \ cdot 2 ^ n [/ math] en un factor de [math] \ frac {n ^ n} {n \ cdot 2 ^ n} = \ frac {(n / 2) ^ n} {n} = \ frac {(n / 2) ^ {n-1}} {2} [/ math]. Dado que esta cantidad aumenta con [matemática] n [/ matemática], está claro que para [matemática] n [/ matemática] suficientemente grande, [matemática] n ^ n [/ matemática] será de hecho la cantidad más grande.

Sin embargo, tenga en cuenta que [math] O (n ^ n) [/ math] no es un límite estricto para [math] n \ cdot 2 ^ n [/ math]. En otras palabras, [matemática] n ^ n [/ matemática] no es la función de crecimiento más lento que podría haber colocado en la gran O. Si desea describir un límite apretado, debe escribir [math] \ Theta (n \ cdot 2 ^ n) [/ math].

Answer 2

Por definición, una función [matemática] f (n) [/ matemática] es [matemática] O (n ^ n) [/ matemática] si existen tales constantes [matemática] C [/ matemática] y [matemática] n_0 [/ matemática] que para cualquier [matemática] n> n_0 [/ matemática] se cumple la condición [matemática] f (n) n_0 [/ math], tenemos [math] n \ times 2 ^ n = n \ times 4 ^ {\ frac {n } {2}}

Answer 3

No lo es. Tome el registro en ambos lados.

LHS: logn + nlog2 = O (n)

RHS: nlogn = O (nlogn)

La igualdad no se mantiene asintóticamente.