请求协助分析递归函数的时间复杂度（预期O(n³)）

我希望帮忙确定以下递归函数的时间复杂度，我初步判断是O(n³)，麻烦帮忙评估：

public static int function(int[] arr, int index) {
    if (index <= 0) {
        return arr[0];
    }

    int one = function(arr, index - 1);
    int two = function(arr, index - 2);
    int three = function(arr, index - 4);

    if (one > two) {
        return one;
    } else if (two > three) {
        return three;
    } else {
        return one;
    }
}

推导过程 #

先定义T(n)为当index = n时函数的总调用次数：

• 当n <= 0时，T(n) = 1（直接返回，仅一次调用）
• 当n > 0时，每次调用会触发3次递归，分别对应n-1、n-2、n-4，再加上当前调用的常数操作，所以递归式是：
  T(n) = T(n-1) + T(n-2) + T(n-4) + O(1)

为什么不是O(n³)？ #

O(n³)是多项式级复杂度，但这个递归的增长速度是指数级的，理由如下：

1. 下界估计：因为T(n-1)是三个递归项里最大的，所以T(n) >= T(n-1) + T(n-2)，而T(n) = T(n-1)+T(n-2)是斐波那契数列的递归式，复杂度是O(φ^n)（φ≈1.618），这里还多了一个T(n-4)项，增长只会更快。
2. 更准确的上界：假设T(n) <= C*r^n，代入递归式可解出r≈1.839（满足r^4 = r^3 + r^2 + 1），说明T(n)是O(r^n)，属于指数级增长，比多项式级的O(n³)快得多。

所以结论是：这个函数的时间复杂度是指数级，具体为O(r^n)（r≈1.839），远高于你初步判断的O(n³)。

内容的提问来源于stack exchange，提问作者Jazi