Calculate Complexity, loop incremented by log(k)

Question

I'm preparing for an exam, and I ran across the following algorithm:

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

I'm trying to work on finding the complexity of the algorithm. Here's what I have so far.

The outside loop obviously runs in n steps. The inside loop gets incremented by log(k), so it should run faster than n as log(n) when n>= 2 is greater than 1. Overall, it looks like the overall complexity is a little faster O(n^2), but by how much? I guess the question boils down to: How do I find the complexity of the inner loop when it is incremented by a function of k? What is the final complexity in this case? I'm assuming O(n^2) is technically correct since it will still be an upper bound, but is there a more accurate answer here?

• Raphael: Community votes, please: duplicate?
• Raphael: Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction.
• gnasher729: There's a problem with k = 2: Is k an integer? Which logarithm do you mean by log k? If it's natural or base 10 then log 2 < 1, so what happens if you increase k = 2 by a number less than 1? You might get stuck right there forever.

Answer 1

Let's ignore the outer loop, and concentrate only on the inner one. Since $\log m \approx \log (2m)$ for $m \geq 2,ドル we see that the number of times it takes $k$ to double is proportional to $k/\log k$. Therefore the number of iteration it takes to get from 2ドル$ to $n$ (assuming for simplicity that $n$ is a power of 2ドル$) is roughly $$ \frac{2}{\log 2} + \frac{4}{\log 4} + \frac{8}{\log 8} + \cdots + \frac{n}{\log n} \approx \frac{n}{\log n}, $$ since the numbers increase exponentially. Therefore the inner loop runs in time $O(n/\log n)$.

You can make this reasoning rigorous with enough effort.