Предыдущий код можно ускорить, если не делать рекурсивные вызовы с одинаковыми аргументами. Вот так:

int FastPower(int x, int n)
{
	if (n == 0) return 1;
	int halfPower = FastPower(x, n / 2);
	int result = halfPower * halfPower;
	if (n % 2 == 0) return result;
	else return result * x;
}

1. Какая сложность у FastPower? 1 балл

Θ(1)

Θ(log(n))

Θ(n)

Θ(n log(n))

Θ(n²)