What is the time complexity of a recursive function with this structure

void f(int n)
{
    if (n == 0)
        return;
    for (int i = n; i >= 1; --i)
    {
        // something O(1)
        f(n - i);
    }
}

My thinking is that it follows

T(n) = T(0)   ...   T(n-2)   T(n-1) = (T(0)   ...   T(n-2))   T(n-1) = T(n-1)   T(n-1) = 2T(n-1)

so we would say O(2^n-1)?

or is it

T(n) = T(0) * ... * T(n-1)

CodePudding user response：

Your analysis seems to be sound.

When in doubt you can measure it. If the complexity really is O(2^n) then you can count how often the inner loop is executed and for increasing n the count divided by 2^n should converge:

#include <iostream>

struct foo {
    int counter = 0;
    void f(int n) {
        if (n == 0)
            return;
        for (int i = n; i >= 1; --i) {
              counter;
            f(n - i);
        }
    }
};

int main() {
    for (int i=0;i < 4;  i) {
        long int n = 2<<i;
        foo f;
        f.f(n);        
        std::cout << n << " " << (2<<n) << " " << f.counter / static_cast<double>(2<<n)  << "\n";
    }
}

Output is:

2 8 0.375
4 32 0.46875
8 512 0.498047
16 131072 0.499992

Note that this measurement cannot prove your analysis to be correct. Though the count seems to converge to 0.5 and the measurement cannot falsify your analysis. The count seems to somewhere around 2^n-1, just that for complexity a constant factor of 2 does not matter and you can write it as O(2^n).

PS: Complexity is interesting when considering algorithms. When considering concrete implementations things are a little different. Note that the function as written can be optimized to an equivalent void f(int) {} which is obviously not O(2^n).