0

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)

Hamideh
  • 115

1 Answers1

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.

mvw
  • 34,562
  • Yes, so the order of magnitude of number the of steps is $O(n3^n)$. $3^n$ is good for a lower bound but is not good for an upper bound. I don't see if $\Theta(n3^n)$ as possible choice. – zoli Mar 22 '17 at 10:25
  • Simply because it is not $O(n 3^n)$, just $O(3^n)$. – mvw Mar 22 '17 at 10:26
  • Oh, stupid of me. The $n$ is in the summation when we compute the sum of the geometric series... – zoli Mar 22 '17 at 10:28