2
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.