递归函数c++的复杂性。

Question

*我想计算以下函数的复杂度大θ符号：变量i是常数==3*。

void g(int i, int n) {
    if (i>0) {
        for (int j=n+10; j>0; j-=5) {
            g(i-2, n);
        }
    }
}

因为是递归函数，所以我认为应该用主定理来计算，但实际上并没有n的划分，如果能得到任何帮助，我将会非常感激

Answer 1

递归关系为T(i，n)=(n+10)T(i-2，n)5。

奇数和偶数的项 i 是乘法系数为(n+10)5的几何级数。这就解决了T(i，n)=O((n5)^(i2))，或者O(sqrt(n5)^i)，如果你喜欢的话。