1
$\begingroup$

I have an algorithm here and it wants me to calculate the complexity:

for (i=1;i<n;i++)
  for (j=1;j<i*i;j++)
    if (j%i==0)
       for (k=0;k<j;k++)
          sum++;

First of all, I think that i have different complexities for best, average and worst case but I don't know how to find them. I have one though and I said that in the best case I will have the 2 fors and count as operation the 'if'. So i have a double sum (ΣΣ 1) with bounds being the values of i,j in the for loops. That's all i did.

Improve this question
$\endgroup$
  • $\begingroup$ In addition to our reference question covering this, you may want to search for questions about algorithm-analysis+loops. $\endgroup$ – Raphael♦ Jun 7 '17 at 21:44
0
$\begingroup$

The number of times that the if is executed is $$ \sum_{i=1}^{n-1} (i^2-1) = \Theta(n^3). $$ The number of times that sum is incremented is $$ \sum_{i=1}^{n-1} \sum_{\substack{1 \leq j < i^2 \\ i \mid j}} j = \sum_{i=1}^{n-1} \sum_{k=1}^{i-1} ki = \sum_{i=1}^{n-1} i \binom{i}{2} = \Theta(n^4). $$ Altogether, we get a running time of $\Theta(n^4)$.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your reply. This is for all occasions? Isn't there separation of best, average, worst case? $\endgroup$ – Georgio3 Jun 7 '17 at 19:17
  • $\begingroup$ The running time here only depends on $n$, so there is only one case, which is both the best case and the worst case, as well as the average case. These distinctions are only meaningful when the algorithm has other inputs, such as an array of length $n$. $\endgroup$ – Yuval Filmus Jun 7 '17 at 19:18
  • $\begingroup$ Duhh there are many opinions. Some find it n^5. Anyway, thank you very much for your reply, you helped! $\endgroup$ – Georgio3 Jun 7 '17 at 19:40
  • $\begingroup$ It's true that $O(n^5)$ is a trivial upper bound, but this upper bound can actually be improved to the tight bound $\Theta(n^4)$. Those who guess $n^5$ are ignoring the if. $\endgroup$ – Yuval Filmus Jun 7 '17 at 19:43
  • 1
    $\begingroup$ Note that there are no "opinions". One opinion is true, and the others are false. That's the way it works in mathematics. $\endgroup$ – Yuval Filmus Jun 7 '17 at 19:43

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