假设x为常数（即，我们对作为x的函数的增长率不感兴趣），expIterative也只是n的函数，并且仅在n〈= 4的情况下调用。存在expIterative在x和n上运行所花费的某个最大时间t *，其中n从0到4。我们可以简单地将该最大时间t * 用作常数，因为可以作为输入发送的N的范围是有界的。

double expRecursive(double x, int n) {
    if (n <= 4) {                                       // a+b
        return expIterativ(x, n);                       // c+t*
    }

    return expRecursive(x, n/2) *                       // c+T(n/2)
           expRecursive(x, (n + 1)/2);                  // d+T((n+1)/2)
}

正如你所指出的，我们可以做一个简化假设，即n是偶数，并且只考虑这种情况，如果我们假设n是2的幂，那就更容易了，因为所有的递归调用都是偶数。
我们得到

T(n) <= 2T(n/2) + (a+b+2c+d+t*)

最后括号里的内容就是常数之和，所以我们可以把它们加在一起，并把结果称为k：

T(n) <= 2T(n/2) + k

我们可以在这里写出一些术语：

n    T(n)
4    t*
8    2t* + k
16   4t* + 2k + k
32   8t* + 4k + 2k + k
...
2^n  2^(n-2)t* + 2^(n-2)k - k
   = (2^n)(t* + k)/4 - k

所以对于一个输入2^n，所需时间与2^n成正比，这意味着T（n）= O（n）。