递归函数的复杂度 c++

Question

*我正在尝试计算以下函数的复杂度 Big-Theta-Notation： 变量 i 是常量 == 3 *

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

因为是递归函数，本以为应该用Master Theorem算一下，结果居然没有n的除法。如果有任何帮助，我将不胜感激！

Answer 1

递推关系为T(i, n) = (n+10)T(i-2, n)/5.

奇数项和偶数项i都是等比级数，乘数为(n+10)/5。如果您愿意，这将解决 T(i, n) = O((n/5)^(i/2))，或 O(sqrt(n/5)^i)。