c - 递归函数的增长顺序

Question

以下问题是在GRE 计算机科学考试 2001中提出的。

Q-67：考虑以下C 代码。

int f(int x) {
    if(x<1) {
        return 1;
    } else {
        return f(x-1)+g(x);
    }
}

int g(int x) {
    if(x<2) {
        return 1;
    } else {
        return f(x-1)+g(x/2);
    }   
}

以下哪项最能描述f(x)作为 x 的函数的增长？

(A)对数 (B)线性 (C)二次 (D)三次 (E)指数

顺便说一句，正确答案是（E）指数（在其答案键中提到）。但是，我不知道解决这个问题的确切方法。

任何人都可以解决上述重复关系吗？你有任何替代方法吗？

请分享您的观点。

Answer 1

我认为这可以简化为 f(x) >= f(x-1)+f(x-1) for x>1，因为g(x) = f(x-1)+g(x/2) >= f(x-1) for x>1。第一个不等式是f(x) >= 2*f(x-1)，从这里很容易推导出f(x) >= 2^x*f(1)（f至少双倍的值每次x增长 1）。