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









up vote
0
down vote

favorite












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!










share|improve this question























  • FLIP is O(1), I couldn't find the edit button for some reason :X, and I got the expression in the title by trying with a sample array of size 10, in the first iteration of the outer loop, the inner loop will iterate 10 times, in the second one the inner loop will iterate 5 times and the third time will iterate 3 times and so on..
    – stylo
    Nov 10 at 16:01











  • The edit button is right under your question. If you cannot find it, use your browser "search on page" function. For more info see Harmonic series.
    – n.m.
    Nov 10 at 16:12







  • 1




    @RoryDaulton, note the k = k + i in the pseudo code (not k = k + 1).
    – trincot
    Nov 10 at 16:13














up vote
0
down vote

favorite












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!










share|improve this question























  • FLIP is O(1), I couldn't find the edit button for some reason :X, and I got the expression in the title by trying with a sample array of size 10, in the first iteration of the outer loop, the inner loop will iterate 10 times, in the second one the inner loop will iterate 5 times and the third time will iterate 3 times and so on..
    – stylo
    Nov 10 at 16:01











  • The edit button is right under your question. If you cannot find it, use your browser "search on page" function. For more info see Harmonic series.
    – n.m.
    Nov 10 at 16:12







  • 1




    @RoryDaulton, note the k = k + i in the pseudo code (not k = k + 1).
    – trincot
    Nov 10 at 16:13












up vote
0
down vote

favorite









up vote
0
down vote

favorite











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!










share|improve this question















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!







algorithm math time-complexity calculus






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 10 at 16:13

























asked Nov 10 at 15:50









stylo

458




458











  • FLIP is O(1), I couldn't find the edit button for some reason :X, and I got the expression in the title by trying with a sample array of size 10, in the first iteration of the outer loop, the inner loop will iterate 10 times, in the second one the inner loop will iterate 5 times and the third time will iterate 3 times and so on..
    – stylo
    Nov 10 at 16:01











  • The edit button is right under your question. If you cannot find it, use your browser "search on page" function. For more info see Harmonic series.
    – n.m.
    Nov 10 at 16:12







  • 1




    @RoryDaulton, note the k = k + i in the pseudo code (not k = k + 1).
    – trincot
    Nov 10 at 16:13
















  • FLIP is O(1), I couldn't find the edit button for some reason :X, and I got the expression in the title by trying with a sample array of size 10, in the first iteration of the outer loop, the inner loop will iterate 10 times, in the second one the inner loop will iterate 5 times and the third time will iterate 3 times and so on..
    – stylo
    Nov 10 at 16:01











  • The edit button is right under your question. If you cannot find it, use your browser "search on page" function. For more info see Harmonic series.
    – n.m.
    Nov 10 at 16:12







  • 1




    @RoryDaulton, note the k = k + i in the pseudo code (not k = k + 1).
    – trincot
    Nov 10 at 16:13















FLIP is O(1), I couldn't find the edit button for some reason :X, and I got the expression in the title by trying with a sample array of size 10, in the first iteration of the outer loop, the inner loop will iterate 10 times, in the second one the inner loop will iterate 5 times and the third time will iterate 3 times and so on..
– stylo
Nov 10 at 16:01





FLIP is O(1), I couldn't find the edit button for some reason :X, and I got the expression in the title by trying with a sample array of size 10, in the first iteration of the outer loop, the inner loop will iterate 10 times, in the second one the inner loop will iterate 5 times and the third time will iterate 3 times and so on..
– stylo
Nov 10 at 16:01













The edit button is right under your question. If you cannot find it, use your browser "search on page" function. For more info see Harmonic series.
– n.m.
Nov 10 at 16:12





The edit button is right under your question. If you cannot find it, use your browser "search on page" function. For more info see Harmonic series.
– n.m.
Nov 10 at 16:12





1




1




@RoryDaulton, note the k = k + i in the pseudo code (not k = k + 1).
– trincot
Nov 10 at 16:13




@RoryDaulton, note the k = k + i in the pseudo code (not k = k + 1).
– trincot
Nov 10 at 16:13












2 Answers
2






active

oldest

votes

















up vote
2
down vote













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)).






share|improve this answer




















  • I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
    – stylo
    Nov 10 at 17:14










  • @stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
    – OmG
    Nov 10 at 18:33

















up vote
0
down vote













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.






share|improve this answer
















  • 1




    There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
    – n.m.
    Nov 10 at 19:49










Your Answer






StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53240625%2fformula-for-the-sum-of-nn-2n-3-n-n%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
2
down vote













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)).






share|improve this answer




















  • I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
    – stylo
    Nov 10 at 17:14










  • @stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
    – OmG
    Nov 10 at 18:33














up vote
2
down vote













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)).






share|improve this answer




















  • I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
    – stylo
    Nov 10 at 17:14










  • @stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
    – OmG
    Nov 10 at 18:33












up vote
2
down vote










up vote
2
down vote









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)).






share|improve this answer












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)).







share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 10 at 16:04









OmG

7,28252643




7,28252643











  • I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
    – stylo
    Nov 10 at 17:14










  • @stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
    – OmG
    Nov 10 at 18:33
















  • I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
    – stylo
    Nov 10 at 17:14










  • @stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
    – OmG
    Nov 10 at 18:33















I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
– stylo
Nov 10 at 17:14




I can't understand how the -n has anything to do with this formula? I understand how it got from this (n/1)+(n/2)+...+(n/n) to H(n) which is equal to ln(n) but also I need to multiply everything by n, so it comes to n*ln(n) isn't it?
– stylo
Nov 10 at 17:14












@stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
– OmG
Nov 10 at 18:33




@stylo as I've mentioned because n = o(nlog(n)) (o means little-oh).
– OmG
Nov 10 at 18:33












up vote
0
down vote













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.






share|improve this answer
















  • 1




    There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
    – n.m.
    Nov 10 at 19:49














up vote
0
down vote













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.






share|improve this answer
















  • 1




    There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
    – n.m.
    Nov 10 at 19:49












up vote
0
down vote










up vote
0
down vote









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.






share|improve this answer












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.







share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 10 at 17:54









Shakil

4391313




4391313







  • 1




    There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
    – n.m.
    Nov 10 at 19:49












  • 1




    There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
    – n.m.
    Nov 10 at 19:49







1




1




There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
– n.m.
Nov 10 at 19:49




There is a formula that expresses the asymptotic behaviour of the harmonic series, which is what OP mist likely needs.
– n.m.
Nov 10 at 19:49

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53240625%2fformula-for-the-sum-of-nn-2n-3-n-n%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Top Tejano songwriter Luis Silva dead of heart attack at 64

政党

天津地下鉄3号線