0
$\begingroup$

I try to evaluate the complexity of the following pseudo code:

S=0;
for (i=1; i<n; i++)
  for (j=0; j<n; j+=i)
    S=S+1;

At first it seems pretty straight forward:

First for loop - $n$

and what about the second one? $\sum_{k=1}^{n-1}(\lceil\frac{n}{k}\rceil+1) + \sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$

so the answer should be something like : $n+n-1+\sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil + \sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$

now I think that $\sum_{k=1}^{n-1}\frac{n}{k}$ is a harmonic series so $\sum_{k=1}^{n-1}\frac{n}{k}=O(nlog(n))$ (this is only the harmoic part without the rest is it correct??)

But what can I do if it is $\sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$?

Please help me figure it out.

$\endgroup$
  • $\begingroup$ You have a mistake in your computation. the result is $O(n\log(n))$. You've missed $n$. $\endgroup$ – OmG Aug 26 '17 at 7:44
  • $\begingroup$ Suppose the $j$ loop were not there at all, or were for (j = 0; j < 1; j++). Then then answer would be $\Theta(n)$. So by doing MORE work, there's no way you get $O(\log n)$. $\endgroup$ – John Hughes Aug 26 '17 at 7:44
  • $\begingroup$ Also, for complexity case you can ignore the ceil function. $\endgroup$ – OmG Aug 26 '17 at 7:45
  • $\begingroup$ @OmG you mean that $\sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$ is $O(nlog(n))$? $\endgroup$ – misha312 Aug 26 '17 at 7:47
  • $\begingroup$ @misha312 yes, it is. $\endgroup$ – OmG Aug 26 '17 at 7:48
1
$\begingroup$

You have a mistake in your computation. the result is $O(n\log(n))$. You've missed $n$ in your final result.

Also, for the complexity case you can ignore the ceil function. Because at most the difference between each item $\lceil \frac{n}{k}\rceil$ and $\frac{n}{k}$ is $1$ , then you can ignore it for the complexity case. it means it does not change the complexity, as it would be $O(n\log(n) + n) = O(n\log(n))$.

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