I don't understand how the time complexity for this algorithm is calculated











up vote
12
down vote

favorite
1












int j=0;

for (int i=0; i<N; i++) 

{

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1; 

}


This code is said to have the time complexity of O(n), but I don't really get it. The inner loop is executed N times and the outer should be also N times? Is it maybe because of the j = 0; outside the loop that is making it only run N times?



But even if it would only run N times in the inner loop, the if statment check should be done also N times, which should bring the total time complexity to O(n^2)?






c algorithm loops time-complexity big-o







share|improve this question









New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 6




    Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start.
    – algrid
    16 hours ago






  • 1




    The inner loop is not repeatedly executed N times. That will only happen once. Once (j<N-1) is false that loop will never be entered again.
    – WhozCraig
    16 hours ago






  • 1




    Possible duplicate of How to find time complexity of an algorithm
    – cirrusio
    16 hours ago















up vote
12
down vote

favorite
1












int j=0;

for (int i=0; i<N; i++) 

{

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1; 

}


This code is said to have the time complexity of O(n), but I don't really get it. The inner loop is executed N times and the outer should be also N times? Is it maybe because of the j = 0; outside the loop that is making it only run N times?



But even if it would only run N times in the inner loop, the if statment check should be done also N times, which should bring the total time complexity to O(n^2)?






c algorithm loops time-complexity big-o







share|improve this question









New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 6




    Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start.
    – algrid
    16 hours ago






  • 1




    The inner loop is not repeatedly executed N times. That will only happen once. Once (j<N-1) is false that loop will never be entered again.
    – WhozCraig
    16 hours ago






  • 1




    Possible duplicate of How to find time complexity of an algorithm
    – cirrusio
    16 hours ago













up vote
12
down vote

favorite
1









up vote
12
down vote

favorite
1






1





int j=0;

for (int i=0; i<N; i++) 

{

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1; 

}


This code is said to have the time complexity of O(n), but I don't really get it. The inner loop is executed N times and the outer should be also N times? Is it maybe because of the j = 0; outside the loop that is making it only run N times?



But even if it would only run N times in the inner loop, the if statment check should be done also N times, which should bring the total time complexity to O(n^2)?






c algorithm loops time-complexity big-o







share|improve this question









New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct. 











int j=0;

for (int i=0; i<N; i++) 

{

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1; 

}


This code is said to have the time complexity of O(n), but I don't really get it. The inner loop is executed N times and the outer should be also N times? Is it maybe because of the j = 0; outside the loop that is making it only run N times?



But even if it would only run N times in the inner loop, the if statment check should be done also N times, which should bring the total time complexity to O(n^2)?






c algorithm loops time-complexity big-o




c algorithm loops time-complexity big-o






share|improve this question









New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 17 hours ago









Some programmer dude

293k24243403




293k24243403






New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 17 hours ago









lomo133

665




665




New contributor




lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






lomo133 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 6




    Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start.
    – algrid
    16 hours ago






  • 1




    The inner loop is not repeatedly executed N times. That will only happen once. Once (j<N-1) is false that loop will never be entered again.
    – WhozCraig
    16 hours ago






  • 1




    Possible duplicate of How to find time complexity of an algorithm
    – cirrusio
    16 hours ago














  • 6




    Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start.
    – algrid
    16 hours ago






  • 1




    The inner loop is not repeatedly executed N times. That will only happen once. Once (j<N-1) is false that loop will never be entered again.
    – WhozCraig
    16 hours ago






  • 1




    Possible duplicate of How to find time complexity of an algorithm
    – cirrusio
    16 hours ago








6




6




Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start.
– algrid
16 hours ago




Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start.
– algrid
16 hours ago




1




1




The inner loop is not repeatedly executed N times. That will only happen once. Once (j<N-1) is false that loop will never be entered again.
– WhozCraig
16 hours ago




The inner loop is not repeatedly executed N times. That will only happen once. Once (j<N-1) is false that loop will never be entered again.
– WhozCraig
16 hours ago




1




1




Possible duplicate of How to find time complexity of an algorithm
– cirrusio
16 hours ago




Possible duplicate of How to find time complexity of an algorithm
– cirrusio
16 hours ago












1 Answer
1






active

oldest

votes

















up vote
14
down vote



accepted










The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.



Indeed if we take a look at the body of the for loop, we see:



while ( (j<N-1) && (A[i]-A[j] > D) )

    j++;


That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.



If we take a look at the entire for loop, we see:



int j=0;

for (int i=0; i<N; i++) {

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1;

}


It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.



Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.



The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.



The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).



So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).






share|improve this answer



















  • 1




    No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
    – Robert Harvey♦
    16 hours ago






  • 1




    I consider your last example correct usage.
    – Robert Harvey♦
    15 hours ago






  • 2




    @robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
    – rici
    15 hours ago






  • 1




    Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
    – Willem Van Onsem
    15 hours ago






  • 1




    @Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
    – rici
    15 hours ago











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
});


}
});






lomo133 is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53770381%2fi-dont-understand-how-the-time-complexity-for-this-algorithm-is-calculated%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
14
down vote



accepted










The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.



Indeed if we take a look at the body of the for loop, we see:



while ( (j<N-1) && (A[i]-A[j] > D) )

    j++;


That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.



If we take a look at the entire for loop, we see:



int j=0;

for (int i=0; i<N; i++) {

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1;

}


It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.



Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.



The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.



The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).



So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).






share|improve this answer



















  • 1




    No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
    – Robert Harvey♦
    16 hours ago






  • 1




    I consider your last example correct usage.
    – Robert Harvey♦
    15 hours ago






  • 2




    @robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
    – rici
    15 hours ago






  • 1




    Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
    – Willem Van Onsem
    15 hours ago






  • 1




    @Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
    – rici
    15 hours ago















up vote
14
down vote



accepted










The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.



Indeed if we take a look at the body of the for loop, we see:



while ( (j<N-1) && (A[i]-A[j] > D) )

    j++;


That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.



If we take a look at the entire for loop, we see:



int j=0;

for (int i=0; i<N; i++) {

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1;

}


It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.



Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.



The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.



The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).



So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).






share|improve this answer



















  • 1




    No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
    – Robert Harvey♦
    16 hours ago






  • 1




    I consider your last example correct usage.
    – Robert Harvey♦
    15 hours ago






  • 2




    @robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
    – rici
    15 hours ago






  • 1




    Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
    – Willem Van Onsem
    15 hours ago






  • 1




    @Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
    – rici
    15 hours ago













up vote
14
down vote



accepted







up vote
14
down vote



accepted






The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.



Indeed if we take a look at the body of the for loop, we see:



while ( (j<N-1) && (A[i]-A[j] > D) )

    j++;


That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.



If we take a look at the entire for loop, we see:



int j=0;

for (int i=0; i<N; i++) {

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1;

}


It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.



Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.



The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.



The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).



So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).






share|improve this answer














The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.



Indeed if we take a look at the body of the for loop, we see:



while ( (j<N-1) && (A[i]-A[j] > D) )

    j++;


That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.



If we take a look at the entire for loop, we see:



int j=0;

for (int i=0; i<N; i++) {

    while ( (j<N-1) && (A[i]-A[j] > D) )

        j++;

    if (A[i]-A[j] == D) 

        return 1;

}


It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.



Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.



The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.



The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).



So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).







share|improve this answer














share|improve this answer



share|improve this answer








edited 15 hours ago

























answered 16 hours ago









Willem Van Onsem

142k16135226




142k16135226








  • 1




    No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
    – Robert Harvey♦
    16 hours ago






  • 1




    I consider your last example correct usage.
    – Robert Harvey♦
    15 hours ago






  • 2




    @robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
    – rici
    15 hours ago






  • 1




    Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
    – Willem Van Onsem
    15 hours ago






  • 1




    @Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
    – rici
    15 hours ago














  • 1




    No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
    – Robert Harvey♦
    16 hours ago






  • 1




    I consider your last example correct usage.
    – Robert Harvey♦
    15 hours ago






  • 2




    @robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
    – rici
    15 hours ago






  • 1




    Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
    – Willem Van Onsem
    15 hours ago






  • 1




    @Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
    – rici
    15 hours ago








1




1




No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
– Robert Harvey♦
16 hours ago




No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase.
– Robert Harvey♦
16 hours ago




1




1




I consider your last example correct usage.
– Robert Harvey♦
15 hours ago




I consider your last example correct usage.
– Robert Harvey♦
15 hours ago




2




2




@robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
– rici
15 hours ago




@robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true g(X) times, where g(X) is a function mapping algorithm input X to integers. If I can also demonstrate that g(X) is in O(f(|X|)) for some function f which maps integers to integers, then I am completely justified in saying the loop executes O(f(N)) times where N is the size of the problem. Why shouldn't I?
– rici
15 hours ago




1




1




Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
– Willem Van Onsem
15 hours ago




Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics
– Willem Van Onsem
15 hours ago




1




1




@Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
– rici
15 hours ago




@Robert: perhaps you disagree but I don't like saying that something happens at most n times when it can happen 2n times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care...
– rici
15 hours ago










lomo133 is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















lomo133 is a new contributor. Be nice, and check out our Code of Conduct.













lomo133 is a new contributor. Be nice, and check out our Code of Conduct.












lomo133 is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53770381%2fi-dont-understand-how-the-time-complexity-for-this-algorithm-is-calculated%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

Quarter-circle Tiles

Image
up vote 0 down vote favorite I have $99$ identical square tiles, each with a quarter-circle drawn on it like this: [asy] size(1.5cm); draw(Arc((2,0),1,90,180),red+1); draw((0,0)--(2,0)--(2,2)--(0,2)--(0,0)); [/asy] When I arrange the tiles in a $9times 11$ rectangular grid, each with a random orientation, what is the expected value of the number of full circles I form? I think this problem has to do with finding the chance any given 2x2 square has a circle, but I can't find it. expected-value share | cite | improve this question asked Nov 20 at 15:03 6minecraftninja 1 2
Read more

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

Image
0 I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $epsilon$ -transition from the start state to the actual finite states of the given automaton. The start state of the given automaton will be my accepting(finite) state of my new one. All transitions will be reversed of course to recognize the reversed word. But how do I have to change the stack of the pushdown automaton? That's tricky. formal-languages automata context-free-grammar share | cite | improve this question edited Nov 29 '18 at 14:20 joee
Read more

Mont Emei

Image
Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog
Read more