¿Puedes ayudarme a encontrar las notaciones Omega, Theta y Big O para la siguiente ecuación?

Question

¿Puedes ayudarme a encontrar las notaciones Omega, Theta y Big O para la siguiente ecuación?

$T(n)=\left(\frac{n+3}{n}\right)^n$

Lo he intentado, pero no estoy seguro de estar avanzando en la dirección correcta para solucionarlo.

Para la notación Big-O ..

$$0\leq T(n)\leq c \cdot g(n)$$

$$0\leq \left(\frac{n+3}{n}\right)^n \leq n^n$$

$$O(n^n) \forall n \geq 3$$

Para $\Omega$ Notación ..

$$0 \leq c\cdot g(n) \leq T(n) $$

$$ 0 \leq n^n \leq \left(\frac{n+3}{n}\right)^n$$

$$\Omega(n^n) \forall 0 < n < 3$$

¿Es correcto? Ayúdame con esto.

Answer 1

Aunque tu complejidad Big O es correcta, no es el límite más estricto, y por lo tanto no puedes obtener la complejidad Theta usando eso.

La pista clave es utilizar el límite $\lim_{n\to\infty}\left(\frac{n+3}{n}\right)^n=\lim_{n\to\infty}\left(1+\frac{3}{n}\right)^n=e^3$ usando el cual puedes probar que esto es en realidad $\Theta(1)$