Encontrar un presupuesto grande O $f(n)=2f(\sqrt{n})+\log n$

Question

Mientras que la auto-estudio de la Matemática Discreta, me encontré con la siguiente pregunta en el libro "Matemática Discreta y Sus Aplicaciones" de Rosen:

Supongamos que la función de $f$ satisface la relación de recurrencia $f(n)=2f(\sqrt{n})+\log n$ siempre $n$ es un cuadrado perfecto mayor que 1 y $f(2)=1$.

Encontrar un big-O estimación de $f(n)$ [Sugerencia: Hacer la sustitución $m=\log n$.]

(Nota: aquí, $\log n$ significa logaritmo en base 2 de $n$.)

En esta solución, se supone que debo utilizar la siguiente variante de la Maestría Teorema:

Maestro Teorema. Deje $f$ será cada vez más una función que satisface la relación de recurrencia

$$f(n)=af(n/b)+cn^d$$

siempre que $n=b^k$ donde $k$ es un número entero positivo, $a\geq 1$, $b$ es un número entero mayor que 1, y $c$ $d$ son números reales con a $c$ positivas y $d$ no negativo. Entonces

$$\begin{align}f(n)&\text{is }\begin{cases} O(n^d)&\text{ if $de < b^d$,} \\ O(n^d\log n)&\text{ if $a = b^d$,} \\ O(n^{\log_b a})&\text{ if $a > b^d$.} \end{cases}\end{align}$$

He resuelto de la siguiente manera, pero no estoy seguro de si esto es correcto:

Siguiendo la sugerencia, he hecho la sustitución $m = \log n$. A continuación, $n=2^m$. La reescritura de la recurrencia de la relación con este valor de $n$:

$$f(2^m)=2f(\sqrt{2^m})+\log (2^m)\text{ with }f(2)=1$$

$$f(2^m)=2f(2^{m/2})+m\text{ with }f(2)=1$$

(debido a que $\sqrt{2^m}=2^{m/2}$$\log (2^m)=m$.)

Para simplificar el análisis, voy a reescribir la recurrencia de la relación anterior para $T(m)=f(2^m)$:

$$T(m)=2T(\dfrac{m}{2})+m\text{ with }T(1)=1$$

Ahora voy a aplicar el Teorema Maestro para $T(m)$. En este caso, $d=1$, $b=2$ y $a=2$, esta relación de recurrencia cumple la condición $a=b^d$ en el Maestro Teorema; por lo tanto:

$$T(m)\text{ is }O(m^d\log m)=O(m\log m)$$

Ahora voy a reescribir la estimación anterior en términos de $f(n)$, sustituyendo $T(m)=f(2^m)=f(2^{\log n})=f(n)$$m=\log n$:

$$f(n)\text{ is } O(\log n\log \log n)$$

Es esta la solución correcta? Si sí, ¿hay alguna manera de simplificar aún más?

Answer 1

Vamos a usar la recursividad de los árboles (también conocido como "la prueba del teorema Maestro")!

• La raíz del árbol de recursión para $f(n)$ valor $\log n$.

• Cada niño de la raíz tiene valor $\log \sqrt{n} = (\log n)/2$, por lo que el valor total de todos los nodos en la profundidad de $1$$\log n$.

• (Verificación de cordura:) Cada nieto de la raíz tiene valor $\log \sqrt{\sqrt{n}} = (\log n)/4$. Por lo que el valor total de todos los $4$ nodos en el nivel $2$$\log n$.

• Un sencillo argumento inductivo implica que para cualquier $\ell$, el valor total de la $2^\ell$ nodos en el nivel $\ell$$\log n$.

• Por lo tanto, todos los cálculos son idénticos, lo que implica que $f(n) = \Theta(L\log n)$ donde $L$ es el número de niveles.

• Otro argumento inductivo implica que cada subárbol cuya raíz está en el nivel de $L$ representa la función de $f(n^{2^{-L}})$. Así que la recursividad fondos a cabo en el menor nivel de $L$ tal que $n^{2^{-L}} \le 2$. (No hay nada especial sobre el número 2 de aquí, cualquier constante mayor que 1 va a hacer.) Tenemos $$ n^{2^{L}} \le 2 \iff 2^{L}\log n \le 1 \ffi \log n \le 2^L \ffi L \le \log\log n. $$

• Llegamos a la conclusión de que $f(n) = \Theta(\log n \log \log n)$.