Si el número dado es [matemática] n [/ matemática], veamos cuál es el tamaño del conjunto que contiene todos los números menores que [matemática] n [/ matemática] de la forma [matemática] a ^ b [/ matemática] donde [matemáticas] a, b> 1 [/ matemáticas]. Si podemos generar este conjunto, entonces solo tenemos que verificar si se puede formar un número dado tomando dos elementos de este conjunto, lo que se puede hacer fácilmente en tiempo lineal en términos de tamaño del conjunto.
Obviamente, [math] a <\ sqrt {n} [/ math], por lo que un límite superior no tan estricto en el tamaño de este conjunto se puede decir como [math] \ sum_ {i = 2} ^ {\ sqrt {n}} \ log_ {i} {n} [/ math] que es claramente menor que [math] \ sqrt {n} * \ log_ {2} {n} [/ math]. A continuación, ordenará este conjunto antes de aplicar su algoritmo de dos punteros o lo que sea, por lo que un límite superior suelto en la complejidad es [matemática] O (\ sqrt {n} * (\ log_ {2} {n}) ^ 2) [ /matemáticas].