En realidad, después de algunas manipulaciones, puede utilizar el teorema maestro! Vamos a ver cómo. En primer lugar, vamos a demostrar el siguiente lema:
Lema: La función de $T$ es no decreciente, es decir, $T(n) \leq T(n+1)$ para todos los $n \in \mathbb{N}$.
Prueba. Por la fuerte inducción en $n \in \mathbb{N}$.
Los casos de Base: Para todos los $0 \leq n \leq 6$, uno ha $T(n) = 1 = T(n+1)$. Por otra parte, $T(7) = 1 < 2\,T(0) + 8^{\pi/2} = T(8)$, $\big\lfloor \frac{8}{\sqrt{2}} \big\rfloor =5$.
Inductivo paso: Vamos a $n > 7$. La fuerte inducción hipótesis es $T(k) \leq T(k+1)$ para todos los $0 \leq k < n$. El objetivo es demostrar que $T(n) \leq T(n+1)$.
Por definición,
\begin{align}
T(n) &= 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2}
&
T(n+1) &= 2\,T\big(\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2}\,.
\end{align}
De acuerdo a las propiedades de la planta de la función, $\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + \big\lfloor \frac{1}{\sqrt{2}} \big\rfloor + 1 = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + 1$, e $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + \big\lfloor \frac{1}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor$, desde el $\sqrt{2} > 1$.
Por lo tanto, sólo hay dos casos:
- cualquiera de las $\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor$ y, a continuación, $T(n) \leq 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2} = T(n+1)$, donde la desigualdad se cumple, porque a partir de $\frac{\pi}{2} > 0$ se sigue que $n^\frac{\pi}{2} < (n+1)^\frac{\pi}{2}$ ;
- o $\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + 1$; podemos aplicar la fuerte inducción de la hipótesis de a $T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 \big)$ porque $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5 < n$ ( $n + 5 > n = \lfloor n \rfloor \geq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor $ desde $\lfloor \cdot \rfloor$ es no decreciente), por lo $T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 \big)\leq T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 + 1\big) = T \big(\big\lfloor \frac{n + 1}{\sqrt{2}} \big\rfloor- 5 \big)$ y, por tanto, $T(n) \leq 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2} = T(n+1)$. $\qquad\square$
Como $T$ es no decreciente por el lema anterior (y $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5 < \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor \leq \frac{n}{\sqrt{2}}$), para $n > 7$ uno ha $T(n) = 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} \leq 2\,T\big(\frac{n}{\sqrt{2}}\big) + n^\frac{\pi}{2}$. Por lo tanto, si ponemos
\begin{align}
S(n) =
\begin{cases}
1 &\text{if } n = 0 \\
2\,S\big(\frac{n}{\sqrt{2}}\big) + n^\frac{\pi}{2} & \text{otherwise}
\end{casos}
\end{align}
a continuación, $T(n) \leq S(n)$ para todos los $n \in \mathbb{N}$ y así, para cualquier función de $g$, $S(n) \in O(g(n))$ implica $T(n) \in O(g(n))$, es decir, el hecho de que $S$ crece asintóticamente no más de $g$ implica que $T$ crece asintóticamente no más de $g$.
El punto es que podemos utilizar el teorema maestro para encontrar una $g$ tal que $S(n) \in O(g(n))$. El uso de las mismas notaciones como en el artículo de la Wikipedia:
\begin{align}
a &= 2 & b&= \sqrt{2} & c_\text{crit} &= \log_\sqrt{2} 2 = 2 & f(n) &= n^{\pi/2}
\end{align}
por lo tanto, $S(n) \in O(n^2)$ por el maestro teorema (desde $\pi/2 < 2 = c_\text{crit}$), y, por tanto, $T(n) \in O(n^2)$.
