I don't understand how the time complexity for this algorithm is calculated
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
edited Dec 13 at 21:35
Some programmer dude
294k24247409
asked Dec 13 at 21:31
lomo133
888
add a comment |
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
edited Dec 13 at 21:35
Some programmer dude
294k24247409
asked Dec 13 at 21:31
lomo133
888
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
Dec 13 at 21:38
1
The inner loop is not repeatedly executedNtimes. That will only happen once. Once(j<N-1)is false that loop will never be entered again.
– WhozCraig
Dec 13 at 21:42
1
Possible duplicate of How to find time complexity of an algorithm
– cirrusio
Dec 13 at 21:44
add a comment |
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
edited Dec 13 at 21:35
Some programmer dude
294k24247409
asked Dec 13 at 21:31
lomo133
888
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
edited Dec 13 at 21:35
Some programmer dude
294k24247409
asked Dec 13 at 21:31
lomo133
888
edited Dec 13 at 21:35
Some programmer dude
294k24247409
asked Dec 13 at 21:31
lomo133
888
edited Dec 13 at 21:35
Some programmer dude
294k24247409
edited Dec 13 at 21:35
Some programmer dude
294k24247409
edited Dec 13 at 21:35
Some programmer dude
294k24247409
294k24247409
asked Dec 13 at 21:31
lomo133
888
asked Dec 13 at 21:31
lomo133
888
asked Dec 13 at 21:31
lomo133
888
888
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
Dec 13 at 21:38
1
The inner loop is not repeatedly executedNtimes. That will only happen once. Once(j<N-1)is false that loop will never be entered again.
– WhozCraig
Dec 13 at 21:42
1
Possible duplicate of How to find time complexity of an algorithm
– cirrusio
Dec 13 at 21:44
add a comment |
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
Dec 13 at 21:38
1
The inner loop is not repeatedly executedNtimes. That will only happen once. Once(j<N-1)is false that loop will never be entered again.
– WhozCraig
Dec 13 at 21:42
1
Possible duplicate of How to find time complexity of an algorithm
– cirrusio
Dec 13 at 21:44
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
Dec 13 at 21:38
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
Dec 13 at 21:38
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
Dec 13 at 21:42
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
Dec 13 at 21:42
1
1
Possible duplicate of How to find time complexity of an algorithm
– cirrusio
Dec 13 at 21:44
Possible duplicate of How to find time complexity of an algorithm
– cirrusio
Dec 13 at 21:44
add a comment |
1 Answer
1
active
oldest
votes
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).
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
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♦
Dec 13 at 22:24
1
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
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 trueg(X)times, whereg(X)is a function mapping algorithm inputXto integers. If I can also demonstrate thatg(X)is inO(f(|X|))for some functionfwhich maps integers to integers, then I am completely justified in saying the loop executesO(f(N))times whereNis the size of the problem. Why shouldn't I?
– rici
Dec 13 at 22:54
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
Dec 13 at 23:09
1
@Robert: perhaps you disagree but I don't like saying that something happens at mostntimes when it can happen2ntimes. 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
Dec 13 at 23:13
|
show 23 more comments
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',
autoActivateHeartbeat: false,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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).
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
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♦
Dec 13 at 22:24
1
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
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 trueg(X)times, whereg(X)is a function mapping algorithm inputXto integers. If I can also demonstrate thatg(X)is inO(f(|X|))for some functionfwhich maps integers to integers, then I am completely justified in saying the loop executesO(f(N))times whereNis the size of the problem. Why shouldn't I?
– rici
Dec 13 at 22:54
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
Dec 13 at 23:09
1
@Robert: perhaps you disagree but I don't like saying that something happens at mostntimes when it can happen2ntimes. 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
Dec 13 at 23:13
|
show 23 more comments
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).
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
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♦
Dec 13 at 22:24
1
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
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 trueg(X)times, whereg(X)is a function mapping algorithm inputXto integers. If I can also demonstrate thatg(X)is inO(f(|X|))for some functionfwhich maps integers to integers, then I am completely justified in saying the loop executesO(f(N))times whereNis the size of the problem. Why shouldn't I?
– rici
Dec 13 at 22:54
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
Dec 13 at 23:09
1
@Robert: perhaps you disagree but I don't like saying that something happens at mostntimes when it can happen2ntimes. 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
Dec 13 at 23:13
|
show 23 more comments
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).
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
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).
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
edited Dec 13 at 23:05
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
answered Dec 13 at 21:40
Willem Van Onsem
143k16135227
143k16135227
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♦
Dec 13 at 22:24
1
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
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 trueg(X)times, whereg(X)is a function mapping algorithm inputXto integers. If I can also demonstrate thatg(X)is inO(f(|X|))for some functionfwhich maps integers to integers, then I am completely justified in saying the loop executesO(f(N))times whereNis the size of the problem. Why shouldn't I?
– rici
Dec 13 at 22:54
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
Dec 13 at 23:09
1
@Robert: perhaps you disagree but I don't like saying that something happens at mostntimes when it can happen2ntimes. 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
Dec 13 at 23:13
|
show 23 more comments
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♦
Dec 13 at 22:24
1
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
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 trueg(X)times, whereg(X)is a function mapping algorithm inputXto integers. If I can also demonstrate thatg(X)is inO(f(|X|))for some functionfwhich maps integers to integers, then I am completely justified in saying the loop executesO(f(N))times whereNis the size of the problem. Why shouldn't I?
– rici
Dec 13 at 22:54
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
Dec 13 at 23:09
1
@Robert: perhaps you disagree but I don't like saying that something happens at mostntimes when it can happen2ntimes. 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
Dec 13 at 23:13
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♦
Dec 13 at 22:24
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♦
Dec 13 at 22:24
1
1
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
I consider your last example correct usage.
– Robert Harvey♦
Dec 13 at 22:46
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
Dec 13 at 22:54
@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
Dec 13 at 22:54
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
Dec 13 at 23:09
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
Dec 13 at 23:09
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
Dec 13 at 23:13
@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
Dec 13 at 23:13
|
show 23 more comments
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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
Dec 13 at 21:38
1
The inner loop is not repeatedly executed
Ntimes. That will only happen once. Once(j<N-1)is false that loop will never be entered again.– WhozCraig
Dec 13 at 21:42
1
Possible duplicate of How to find time complexity of an algorithm
– cirrusio
Dec 13 at 21:44