# Calculate Complexity, loop incremented by log(k)

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?

• Community votes, please: duplicate? – Raphael Oct 18 '16 at 22:25
• 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. – Raphael Oct 18 '16 at 22:26
• 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. – gnasher729 Oct 19 '16 at 7:33

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)$.