Ndtyjky

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

thanks!

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(nlog(n)). The -n has anot any effect on the asymptotic computaional cost, as n = o(nlog(n)).

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.