I am currently trying to determine the Big-Theta complexity of the recursive algorithm below. It makes sense that the complexity is at least n^2 (due to the nested for-loop). However, the recursive aspect makes me struggle to determine its precise Big-Theta complexity.

I guess it must be n^3 as the function calls itself recursively and executes itself. But I struggle to find proof for that. Can anyone please tell me the complexity and how to determine it for recursive algorithms?

function F(n)
    if n < 1: 
        return 1
    t = 0
    for i <- 0 to n:
        for j <- i to n:
            t = t   j
    return t   F(n-1)

CodePudding user response：

The recursion aspect of this algorithm is fairly simple: it comes down to tail recursion and so it can be written as a loop:

function F(n)
    t = 0
    for k <- n to 1:
        for i <- 0 to k:
            for j <- i to k:
                t = t   j
    return t   1

...where k replaces the argument that each recursive call would get as n

The number of times that t = t j executes is determining for the time complexity (assuming addition is considered a Θ(1) step).

This represents a tetrahedral number and is Θ(n³).