Estoy revisando las definiciones formales de Big O y los otros límites asociados y algo me está tropezando. En el libro que estoy leyendo (Skiena) Big O se define como:

f (n) = O (g (n)) cuando existe una constante c tal que f (n) es siempre <= c * g (n) para un valor de n> n0

Esto generalmente tiene sentido para mí. Solo nos interesan los valores lo suficientemente grandes de n como para que las tasas de crecimiento realmente importen. Pero, ¿por qué multiplicar g (n) por c? Parece que podría elegir un valor muy grande para c, y hacer que todo sea arbitrario eliminando el tamaño de los valores g (n) más pequeños.

Pregunta secundaria: al elegir clasificar un algoritmo en una clase de complejidad, ¿la regla general es elegir la clase de crecimiento más baja que aún se mantiene de acuerdo con la definición de Big O? Según la definición, parece válido clasificar un algoritmo de tiempo constante como O (n!), Simplemente porque f (n) será <= c * g (n). Por supuesto, esto no ofrece valor.

¡Gracias!