3
$\begingroup$

How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve sqrt(n) * <something>. I Just don't know what that <something> is.

public void timeComplexity(int[] arr){
    int n = arr.length;
    int sqrt = (int) Math.sqrt(n+1);
    for(int i=2; i<sqrt; i++){
        for(int k= (int) Math.pow(i,2); k < n; k+=i){
            //do some constant time work
        }
    }
}

Also consider the following two variations:

  1. k starts at i (k=i or k=3) instead of k= (int) Math.pow(i,2).
  2. k is incremented by some constant k++ instead of the variable i k+=i
$\endgroup$
2
$\begingroup$

You are interested in several different variants. I'll show you how to estimate the running time in the first one, you do the rest. In fact, I will only estimate the number of times that the inner loop is run, which is $$ \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil. $$ To obtain this, you need to figure out the number of iterations in loops of the form for (x = a; x < b; x += c) (assuming $a \leq b$ and $c \geq 1$), which is a nice exercise.

Using $x \leq \lceil x \rceil < x+1$, we see that the sum above can be bounded by $$ \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} \leq \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil < \lfloor \sqrt{n+1} \rfloor-2 + \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} . $$ Using $m = \lfloor \sqrt{n+1} \rfloor - 1$, we can evaluate the left sum as follows: $$ \sum_{i=2}^m \frac{n-i^2}{i} = n \sum_{i=2}^m \frac{1}{i} - \sum_{i=2}^m i = n (H_m-1) - \frac{m(m+1)}{2} + 1, $$ where $H_m$ is the $m$th harmonic number. It is well-known that $H_m = \log m + O(1)$, and so we can estimate the sum by $\frac{1}{2}n \log n - \Theta(n)$, skipping a few steps. A similar bound holds for the right sum, since the additional term is only $\Theta(\sqrt{n})$. Altogether, we deduce that the inner loop runs $\frac{1}{2}n\log n - \Theta(n)$ many times.

$\endgroup$
  • $\begingroup$ Thank you so much for caring! I was able to follow the explanation very well without any problem. $\endgroup$ – salyela Mar 31 '18 at 20:06

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.