Time complexity of a loop increases by log?

Question

Could someone please help me understanding how I can find the time complexity of the following loops :

    for (int j = 1 to n) {
      k = j;
       while (k < n) {
        sum += a[k] * b[k];
        k += log n;
       }
     }      

I found the solution here which is n² / log(n).

It's obvious that the outer loop takes n times but for the inner one, I'm stuck. Where did the n / log n factor come from?

I tried to follow it term by term but couldn't continue

1st time k = 1,
2nd time k = 1 + log n
3rd time k = 1 + log n + log n  //   (2 log n)

stuck here :(

How could I find a pattern or what is the best steps should I follow to get the time complexity for such code?

Answer 1

Try thinking about it this way: the outer loop definitely runs O(n) times, so if you can determine the amount of work done in the inner loop, you can multiply it by O(n) to get an upper bound on the total work done.

So let's look at the inner loop. Notice that k will take on the values j, j + log n, j + 2 log n, ..., j + i log n as the loop iterates, where i is the number of iterations that the loop has run for.

So think about the maximum number of times that loop can execute. It stops as soon as k ≥ n, which means that it stops as soon as j + i log n ≥ n, so after (n - j) / log n iterations the loop will stop running. If we want to get a conservative upper bound for the number of times this can happen, notice that in the worst case we have j = 1. This means that the maximum number of iterations of this loop is (n - 1) / log n = O(n / log n), so each iteration of the inner loop does O(n / log n) work.

Multiplying O(n / log n) work per loop iteration by O(n) iterations produces the overall result of O(n² / log n), which is the desired result.

Hope this helps!

Answer 2

The outer loop runs in order n, obviously. So the question is: how long does the inner loop take? The loop terminates when k >= n, and k starts at j and increments in steps of log(n). It takes approximately

n / log(n)

iterations to sum from 1 to n in steps of log(n) (give or take rounding error). But we don't always go all the way from 1 to n - sometimes we go from 10 to n, or 20, or n/2... It will take

(n - i) / log(n)

when we start at i instead of 1 (or 0...) We can write the total number of times the inner loop is executed explicitly as a sum:

total number = sum(i = 1 to n, (n - i) / log(n))
             = sum(i = 1 to n, n / log(n)) - sum( i = 1 to n, i / log(n))

             = O(n * n / log(n)) - something smaller than that.

The "smaller term" is about half of the first term since

sum( i = 1 to n, i ) = n * (n + 1) / 2;

But when we look at the order of calculations, a constant like that doesn't matter - we just want to know what happens to the time when n gets larger, so while you might want to say that the algorithm runs in O( (1 - 0.5) * n2/log(n)), we just say that it runs in O( n2/log(n))

Can you see it now?