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!