2
$\begingroup$

Can someone please help me with this problem? Any help would be much appreciated?

Thanks in advance!!

sum = 0;
for (i = n; i > 0; i = i/3)
    for (j = 0; j < n^3; j++)
        sum++;

What is the time complexity (in Θ–notation) in terms of n?

$\endgroup$
3
$\begingroup$

It is typically assumed that addition can be done in constant time, so each time you increment sum, you spend $O(1)$ time (which we'll think of as $1$ unit of time). As that is the only thing that contributes to the time complexity, you just need to figure out how many times you are incrementing sum.

The inner for loop doesn't depend on i, so let's look at that first. For each number j between $0$ and $n^3$, you increment the sum. How many times do you increment sum each time the inner for loop runs? You increment it a total of $n^3$ times.

Now let's look at the outer loop. We again want to know how many times the loop runs. The question is, how many times can you divide $n$ by $3$ before it becomes less than $1$? If you think about it, you'll see that this is very near $\log_3 n$. So the outer loop runs $\log_3 n$ times.

In total, the outer loop runs $\log_3 n$ times, and in each of those runs the inner loop runs $n^3$ times, meaning that sum increments about $n^3 \log_3 n$ times.

$\endgroup$
  • $\begingroup$ You don't need to be as specific as $\log_3$ as $\mathcal{\Theta}\left(\log_a(n)\right)$ is equivalent to $\mathcal{\Theta}\left(\log_b(n)\right)$ (this is because they only differ by a constant). $\endgroup$ – Jared Jun 7 '14 at 6:42
  • $\begingroup$ I really appreciate your help! :D $\endgroup$ – Chrissy Jun 7 '14 at 6:44
1
$\begingroup$

The inner loop is independent of the outer loop variable $i$. The inner loop always loops $n^3$ times. Look at the outer loop, $i$ is initially $n$, therefore after one iteration it is $\frac{n}{3}$, then $\frac{n}{3^2}$, then $\frac{n}{3^3}$. Assuming integer division the outer loop continues (approximately) until $\frac{n}{3^k} < 1$. This means $k \approx \log_3\left(n\right)$. Therefore the the run time would be $\mathcal{\Theta}\left(n^3\log\left(n\right)\right)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.