CODEWITHSUNDEEP
algorithmmathtime-complexitycalculus
stylo
stylo

Reputation: 506

formula for the sum of n+n/2+n/3+...+n/n

so I got this algorithm I need to calculate its time complexity

which goes like

for i=1 to n do
    k=i
    while (k<=n) do
        FLIP(A[k])
        k = k + i

where A is an array of booleans, and FLIP is as it is, flipping the current value. therefore it's O(1).

Now I understand that the inner while loop should be called

n/1+n/2+n/3+...+n/n

If I'm correct, but is there a formula out there for such calculation?

pretty confused here

Upvotes: 3

Views: 9927

Answers (3)

Biswajit Kaushik
Biswajit Kaushik

Reputation: 9

The given problem boils down to calculate below sum -Sum of harmonic series

Although this sum can't be calculated accurately, however you can still find asymptotic upper bound for this sum, which is approximately O(log(n)).

Hence answer to above problem will be - O(nlog(n))

Upvotes: 0

OmG
OmG

Reputation: 18838

The more exact computation is T(n) \sum((n-i)/i) for i = 1 to n (because k is started from i). Hence, the final sum is n + n/2 + ... + n/n - n = n(1 + 1/2 + ... + 1/n) - n, approximately. We knew 1 + 1/2 + ... + 1/n = H(n) and H(n) = \Theta(\log(n)). Hence, T(n) = \Theta(n\log(n)). The -n has not any effect on the asymptotic computaional cost, as n = o(n\log(n)).

Upvotes: 6

Shakil
Shakil

Reputation: 4630

Lets say we want to calculate sum of this equation

  n + n / 2 + n / 3 + ... + n / n
=> n ( 1 + 1 / 2 + 1 / 3 + ..... + 1 / n )

Then in bracket ( 1 + 1 / 2 + 1 / 3 + ... + 1 / n ) this is a well known Harmonic series and i am afraid there is no proven formula to calculate Harmonic series.

Upvotes: 4

Related Questions