Notación Big Oh para la suma

Question

La notación Big Oh es importante para clasificar el comportamiento asintótico de las funciones, pero no sé cómo trabajar con ellas en los sumatorios

Tenemos dos funciones $\ f,g$

$$f(n)=\sum^{\lfloor \log_2 n \rfloor}_{i=1} 3^i$$ $$g(n)=n^2$$

Ahora tengo que determinar qué regla del Big Oh se aplica aquí; en otras palabras, queremos saber si la función $f$ está creciendo más rápido que $g$ etc. o función $g$ está creciendo más rápido que $f$ etc.

(1) $f(n)=\mathcal{O}(g(n))$

(2) $f(n)=\mathcal{o}(g(n))$

(3) $f(n)=\Omega(g(n))$

(4) $f(n)=\omega(g(n))$

(5) $f(n)=\Theta(g(n))$

En general, sé cómo utilizar estas reglas, pero las sumas no son funciones típicas.

Answer 1

Puedes simplificar la suma a algo que te resulte más familiar. En lo anterior, la suma es una suma geométrica, que tiene el valor $$ \sum_{i=0}^N a^i = \frac{a^{N+1}-1}{a-1}. $$ Con $N = \log_2 n$ y $a=3$ (no te preocupes por los pisos ya que no tienen tanta influencia en el comportamiento asintótico), tu $f$ parece algo así como $$ \frac{3^{\log_2 n}}2 = \frac{n^{\log_2 3}}2. $$

Desde $\log_2 3\approx1.58496$ puede esperar que su $f$ para ser más rápido que $n^2$ .