What is the computation complexity of calculating the exact sum of the finite series $$\overset{\sqrt{n}}{\underset{i=2}{\sum }}\frac{n}{i}$$ ?
It can be seen that we need $\ \sqrt{n}-1\ $ multiplications and $\ \sqrt{n}-1\ $ additions. Any kind of help would be greatly appreciated.
That's tricky. There are obviously sqrt(n) divisions and additions. But you are asking for the exact sum. The only way to get the exact sum is to add these values as rational numbers. Say n = 1,000,000, you add n/2 + n/3 + n/4 + ... + n/1000. You will end up with huge fractions with huge numbers of digits.
You can obviously add the integer parts and are left adding fractions all less than 1. The lcm of 2, 3, 4, 5, 6, ..., 1000 will be around 2^1000 (very very rough guess). If you arrange the terms in a binary tree, you should have one sum with a 1,000 digit denominator, two with 500 digit denominators, four with 250 digit denominators etc.
Adding two fractions with k digit denominator takes O(k^2) steps with a straightforward algorithm, or O (k log k) with a very clever algorithm. The total should be about O (n^(1/2) log^2 n) doing multiplications using FFT with a very non-trivial algorithm. Or about O (n log n) with a straightforward algorithm.
Obviously it's your responsibility to check this all more carefully.