What is the time complexity of a recursive function that calls itself N times with one less?

Question

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)

@463035818_is_not_a_number i edited it with a few more steps — yolo expectz, Apr 29 '22 at 16:45
Count how many times `f` is called for `f(0)`, `f(1)`, `f(2)`, `f(3)`, ... until you see a reliable pattern develop. — Matt, Apr 29 '22 at 16:53
Does this answer your question? [Determining complexity for recursive functions (Big O notation)](https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation) — Anand Sowmithiran, Apr 29 '22 at 16:54
@AnandSowmithiran i don't think there is anything similar to mine there — yolo expectz, Apr 29 '22 at 16:57

score 1 · Accepted Answer · answered Apr 29 '22 at 16:59

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).

this is great, but what does the ration tell us? if its 1 then is it exactly 2^n calls? — yolo expectz, Apr 29 '22 at 17:09
@yoloexpectz the exact value does not matter as long as it converges, because constant factors are not relevant for asymptotic complexity. On the other hand the counter does have the constant factors. The counter seems to be close to `2^(n-1)` but `O(2^(n - 1)) == O(0.5*(2^n)) == O(2^(n + 42)) == O(2^42 * 2^n)` and the canonical way to express it is `O(2^n)`. — 463035818_is_not_an_ai, Apr 29 '22 at 17:13
@yoloexpectz I hope its clear in the answer. Dividing by `2^n` only makes sense when you already know that it is `O(2^n)`. Consider you assume complexity is `O(n^2)` then dividing the counter by `n^2` will not converge, and you would know that your analysis was wrong — 463035818_is_not_an_ai, Apr 29 '22 at 17:16

What is the time complexity of a recursive function that calls itself N times with one less?

1 Answers1