Worst-case running time using Big-Θ notation

Question

I understand that the innermost for loop is Θ(logn) and the two outermost for loops is Θ(n^2) because it's an arithmetic sum. The if-statement is my main problem. Does anyone know how to solve this?

int tally=0;
for (int i = 1; i < n; i ++)
{
   for (int j = i; j < n; j ++)
   {
        if (j % i == 0)
        {
            for (int k = 1; k < n; k *= 2)
            { 
                tally++;
            }
        }
   }
}

Answer 1

Edit:
Now I noticed loop order: i before j.

In this case for given i value j varies from i to n and there are (n/i) successful if-conditions.

So program will call then most inner loop

n/1 +n/2+n/3+..+n/n

times. This is sum of harmonic series, it converges to n*ln(n)

So inner loop will be executed n*log^2(n) times.

As you wrote, two outermost loops provide O(n^2) complexity, so overall complexity is O(n^2 + n*log^2(n)), the first term overrides the second one, loop, and finally overall complexity is quadratic.

int tally=0;
for (int i = 1; i < n; i ++)
{  
   // N TIMES
   for (int j = i; j < n; j ++)
   {  
     //N*N/2 TIMES
        if (j % i == 0)
        {
         //NlogN TIMES
            for (int k = 1; k < n; k *= 2)
            { 
             //N*logN*logN
                tally++;
            }
        }
   }
}

---

Old answer (wrong)

This complexity is linked with sum of sigma0(n) function (number of divisors) and represented as sequence A006218 (Dirichlet Divisor problem)

We can see that approximation for sum of divisors for values up to n is

  n * ( log(n) + 2*gamma - 1 ) + O(sqrt(n))

so average number of successful if-conditions for loop counter j is ~log(j)