java - Java递归效率分析

Question

我需要帮助为下面这样的方法创建效率分析。我需要想出：

1. 影响运行时间的因素
2. 什么被计算（比较，操作）？
3. 最好/最坏情况
4. 大 O 符号

这是我到目前为止所拥有的：

1. 数组长度
2. 数学运算
3. 最坏情况和最好情况是相同的，因为该方法将运行整个数组，而不管其内容如何
4. 不知道

让我知道你的想法。

谢谢

double sum(double[] array) {
    return recursiveSum(array, 0, array.length - 1);
}

double recursiveSum(double[] array, int lo, int hi) {
    if (lo == hi) {
        return array[lo];
    }

    int mid = (lo + hi) / 2;
    double leftsum = recursiveSum(array, lo, mid);
    double rightsum = recursiveSum(array, mid+1, hi);
    return leftsum + rightsum;
}

Answer 1

我的答案：

1. 数组长度
2. 不知道
3. 最坏情况和最好情况是相同的，因为该方法将运行整个数组，而不管其内容如何
4. O(nlogn) (f(n)=2*f(n/2) -> f(n)=O(nlogn))