Tuesday, 10 September 2013

How do i compute the sum n+n/2+n/3+n/4........+(n/n) in less than O(n) time?

How do i compute the sum n+n/2+n/3+n/4........+(n/n) in less than O(n) time?

I need an algorithm that has time complexity less than O(n).
Currently I have this algorithm:
int n; sum=n; for(int i=2;i<=n;i++) { sum+=n/i; }

No comments:

Post a Comment