time complexity for my function

Question

What is the time complexity for the following function? (the basic operation is the innermost loop body's assignment).

function f(n)
    r ← 0
    m ← 1
    for i ← 1 to n do
        m ← 3 × m
        for j ← 1 to m do
            r ← r + j
    return r

Multiple Choices:

Θ(n^3)

Θ(3^n)

Θ(n*log(n))

Θ(n)

Θ(n^2)

Answer 1

Let me rewrite it a bit:

function f(n)
    r ← 0
    for i ← 1 to n do
        for j ← 1 to 3^i do
            r ← r + j
    return r

So we have $$ \sum_{i=1}^n 3^i = \frac{3^{n+1} - 1}{3 - 1 } - 1 $$ evaluations of the inner loop.