递归递推式化简与正确性验证：两个递推式是否成立？

算法伪代码 #

int algorithm(int[] a, i, j)
    if i > j
        return 0

    int n = j - i + 1
    int d = n / 4

    algorithm(a, i, i+3d-1)
    algorithm(a, i+d, j)

    return 1 

该算法的主要开销来自两次递归调用。有人推导认为第一次递归调用的规模为3n/4（忽略常数1），第二次为n/4，由此得到递推式：T(n) = T(3n/4) + T(n/4) + O(1)。以下是对两个问题的解答：

问题1：上述递推式是否正确？ #

不正确。我们直接计算两次递归调用的规模：

• 第一次递归调用的区间是[i, i+3d-1]，规模为(i+3d-1) - i + 1 = 3d。由于d = n/4，因此规模为3n/4（渐近分析中可忽略整数除法的取整误差）。
• 第二次递归调用的区间是[i+d, j]，规模为j - (i+d) + 1。结合n = j - i + 1，代入后得(j - i + 1) - d = n - d = n - n/4 = 3n/4。

可见两次递归的规模均为3n/4，而非推导中的3n/4和n/4，因此原递推式错误。

问题2：递推式T(n) = 2T(3n/4) + O(1)是否正确？ #

正确。由上述计算可知，两次递归调用的规模均为3n/4，算法的非递归部分仅包含变量计算、条件判断和返回操作，开销为常数级O(1)，因此该递推式准确描述了算法的时间复杂度递归关系。

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