# Calculate the complexity of an algorithm [duplicate]

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.

## marked as duplicate by Raphael♦Jun 7 '17 at 21:44

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)$.
• 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$. – Yuval Filmus Jun 7 '17 at 19:18
• 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. – Yuval Filmus Jun 7 '17 at 19:43