calculate the number of basic operations in a recursive algorithm

Question

How can I calculate the number of basic operations (additions and subtractions) in terms of Θ?

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) 

these are my multiple choices:

Θ(n^2 log n)

Θ(n)

Θ(n^3)

Θ(n^2)

Θ(n^4)

Answer 1

There are approximately $n$ operations involving $i$. There are are $n-i$ operations involving $j$. And we repeat this $n$ times.

Thus, we have something of order $n^3$, since $n\times n\times n=n^3$.

You can also prove by induction that the number of steps involved are

$$f(n)\to\frac{n(n+1)(n+2)}6+n$$