Con respecto a la parte b, que pregunta si hay otro algoritmo que calcule la potencia, si se usa la función de C++ "pow", eso se consideraría como otro algoritmo que resuelva la potencia de un número? Y, en ese caso, su orden sería menor?
Este es un problema difícil.
en vez de 
sino la mitad del caso original.Primero tratá de resolverlo asumiendo que 
es una potencia de 2.
Por ejemplo si querés calcular 
y ya conocés 
, ¿cómo harías el cálculo? Luego de saber esto, ¿cómo harías para poder calcular ? Tené en cuenta que sabés que 
.
Si sobre esta hay dudas lo seguimos viendo.
Si no, vamos a suponer que es impar, concretamente 1 + potencia de 2, por ejemplo 17. Tendrías 
. Y sabrías como resolverlo.
Por ahí va la solución del caso general: tener en cuenta si es par o impar.