数据结构基础(((x^2+1))^2+1)^2......时间复杂度为什么是2logN

Question

书上原文:

求幂运算, 要计算X^N, 如果N为偶数, 那么X^N = X^(N/2) * X^(N/2) , 如果N为奇数, 那么X^N = X^(N/2) * X^(N/2) * X.
例如: X^62次,算法将如下进行, 它只用到了9次乘法
X^3=(X^2)X, X^7=(X^3)^2X, X^15=(X^7)^2X, X^31=(X^15)^2X, X^62=(X^31)^2
显然, 所需要的乘法次数最多是2logN.

图片:

通过这个例子和一个前辈的指明, 我总结出X^N = ((((x^2)^2+1)^2+1)^2+1)...., 但是如果通过这个求出时间复杂度为2logN?