Mixing
How to count the runtime of an algorithm with an expanding array (which itself is looped) inside a loop?
I have an algorithm for finding a list of primes under N, and also the lowest factor of all the numbers N.
/*
arrLF stands for arrLowestFactor, it stores all the LF
arrPrime is the list of primes under N. The variable pn is used to keep track of how many primes we have discovered. Initially pn is zero.
*/
for(int i = 2; i <= N; i++){
//if a number i hasn't got its lowest factor yet, it means we have discovered a new prime number. And this prime number will be the LF of i too.
if(!arrLF[i]){
arrPrime[pn++] = i;
arrLF[i] = i;
}
//run through the list of prime once and fill up the lowest factor of (i * arrPrime[j]) in the arrLF table
//it's like doing sieve of eratosthenes but we build the table up one at a time
for(int j = 1; i * arrPrime[j] <= N; j++){
arrLF[ i * arrPrime[j] ] = arrPrime[j];
if( i % arrPrime[j] == 0)
break;
}
}
For the outer loop, it's running at O(N). So the running of this algorithm will be O(N * M), where M is the runtime of the inner loop. But since the list of primes is expanding unconsistently, how do I assess complexity of M?
Btw I found this algorithm by studying a solution of a red coder on codeforce, does anyone know this algorithm or its name?
time-complexity
asked Jan 1 at 11:04
JJChaiJJChai
3827
add a comment |
I have an algorithm for finding a list of primes under N, and also the lowest factor of all the numbers N.
/*
arrLF stands for arrLowestFactor, it stores all the LF
arrPrime is the list of primes under N. The variable pn is used to keep track of how many primes we have discovered. Initially pn is zero.
*/
for(int i = 2; i <= N; i++){
//if a number i hasn't got its lowest factor yet, it means we have discovered a new prime number. And this prime number will be the LF of i too.
if(!arrLF[i]){
arrPrime[pn++] = i;
arrLF[i] = i;
}
//run through the list of prime once and fill up the lowest factor of (i * arrPrime[j]) in the arrLF table
//it's like doing sieve of eratosthenes but we build the table up one at a time
for(int j = 1; i * arrPrime[j] <= N; j++){
arrLF[ i * arrPrime[j] ] = arrPrime[j];
if( i % arrPrime[j] == 0)
break;
}
}
For the outer loop, it's running at O(N). So the running of this algorithm will be O(N * M), where M is the runtime of the inner loop. But since the list of primes is expanding unconsistently, how do I assess complexity of M?
Btw I found this algorithm by studying a solution of a red coder on codeforce, does anyone know this algorithm or its name?
time-complexity
asked Jan 1 at 11:04
JJChaiJJChai
3827
add a comment |
I have an algorithm for finding a list of primes under N, and also the lowest factor of all the numbers N.
/*
arrLF stands for arrLowestFactor, it stores all the LF
arrPrime is the list of primes under N. The variable pn is used to keep track of how many primes we have discovered. Initially pn is zero.
*/
for(int i = 2; i <= N; i++){
//if a number i hasn't got its lowest factor yet, it means we have discovered a new prime number. And this prime number will be the LF of i too.
if(!arrLF[i]){
arrPrime[pn++] = i;
arrLF[i] = i;
}
//run through the list of prime once and fill up the lowest factor of (i * arrPrime[j]) in the arrLF table
//it's like doing sieve of eratosthenes but we build the table up one at a time
for(int j = 1; i * arrPrime[j] <= N; j++){
arrLF[ i * arrPrime[j] ] = arrPrime[j];
if( i % arrPrime[j] == 0)
break;
}
}
For the outer loop, it's running at O(N). So the running of this algorithm will be O(N * M), where M is the runtime of the inner loop. But since the list of primes is expanding unconsistently, how do I assess complexity of M?
Btw I found this algorithm by studying a solution of a red coder on codeforce, does anyone know this algorithm or its name?
time-complexity
asked Jan 1 at 11:04
JJChaiJJChai
3827
I have an algorithm for finding a list of primes under N, and also the lowest factor of all the numbers N.
/*
arrLF stands for arrLowestFactor, it stores all the LF
arrPrime is the list of primes under N. The variable pn is used to keep track of how many primes we have discovered. Initially pn is zero.
*/
for(int i = 2; i <= N; i++){
//if a number i hasn't got its lowest factor yet, it means we have discovered a new prime number. And this prime number will be the LF of i too.
if(!arrLF[i]){
arrPrime[pn++] = i;
arrLF[i] = i;
}
//run through the list of prime once and fill up the lowest factor of (i * arrPrime[j]) in the arrLF table
//it's like doing sieve of eratosthenes but we build the table up one at a time
for(int j = 1; i * arrPrime[j] <= N; j++){
arrLF[ i * arrPrime[j] ] = arrPrime[j];
if( i % arrPrime[j] == 0)
break;
}
}
For the outer loop, it's running at O(N). So the running of this algorithm will be O(N * M), where M is the runtime of the inner loop. But since the list of primes is expanding unconsistently, how do I assess complexity of M?
Btw I found this algorithm by studying a solution of a red coder on codeforce, does anyone know this algorithm or its name?
time-complexity
time-complexity
asked Jan 1 at 11:04
JJChaiJJChai
3827
asked Jan 1 at 11:04
JJChaiJJChai
3827
asked Jan 1 at 11:04
JJChaiJJChai
3827
asked Jan 1 at 11:04
JJChaiJJChai
3827
asked Jan 1 at 11:04
JJChaiJJChai
3827
3827
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
your algorithm will run in O(n) . Let me explain why
we need to look at the inner loop to understand why it does not affect time complexity in exponential manner .
the inner loop look will run in worst case the following number of time for each iteration
1st iteration : 1/2 * N times
2nd iteration : 1/3 * N times
3rd iteration : 1/4 * N times
and so on
So the number of times the inner loop is running is decreasing each time we do it .
and we can say the total number of times the inner loop will run is
SUM(1/2 + 1/3 + 1/4 + ... 1/N)
and this is called harmonic series
https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
and although this series converge to infinity, it converge very slowly that for N of 10^43 it is less than 100
so realistically the inner loop will run in worst case constant number of N times lets say 100 times max for java float limit
So that mean the time complexity of the full algorithm is the time complexity of the inner loop because the outer loop does not run any other loops .
So the time complexity will be O(Xn) where X is constant number that as we explained will realistically not exceed 100 or 200 within the numbers limits of java which will mean the total complexity of the algorithm is O(n) since we omit the constant
answered Jan 1 at 12:01
HaniHani
903317
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
add a comment |
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%2f53994934%2fhow-to-count-the-runtime-of-an-algorithm-with-an-expanding-array-which-itself-i%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
your algorithm will run in O(n) . Let me explain why
we need to look at the inner loop to understand why it does not affect time complexity in exponential manner .
the inner loop look will run in worst case the following number of time for each iteration
1st iteration : 1/2 * N times
2nd iteration : 1/3 * N times
3rd iteration : 1/4 * N times
and so on
So the number of times the inner loop is running is decreasing each time we do it .
and we can say the total number of times the inner loop will run is
SUM(1/2 + 1/3 + 1/4 + ... 1/N)
and this is called harmonic series
https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
and although this series converge to infinity, it converge very slowly that for N of 10^43 it is less than 100
so realistically the inner loop will run in worst case constant number of N times lets say 100 times max for java float limit
So that mean the time complexity of the full algorithm is the time complexity of the inner loop because the outer loop does not run any other loops .
So the time complexity will be O(Xn) where X is constant number that as we explained will realistically not exceed 100 or 200 within the numbers limits of java which will mean the total complexity of the algorithm is O(n) since we omit the constant
answered Jan 1 at 12:01
HaniHani
903317
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
add a comment |
your algorithm will run in O(n) . Let me explain why
we need to look at the inner loop to understand why it does not affect time complexity in exponential manner .
the inner loop look will run in worst case the following number of time for each iteration
1st iteration : 1/2 * N times
2nd iteration : 1/3 * N times
3rd iteration : 1/4 * N times
and so on
So the number of times the inner loop is running is decreasing each time we do it .
and we can say the total number of times the inner loop will run is
SUM(1/2 + 1/3 + 1/4 + ... 1/N)
and this is called harmonic series
https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
and although this series converge to infinity, it converge very slowly that for N of 10^43 it is less than 100
so realistically the inner loop will run in worst case constant number of N times lets say 100 times max for java float limit
So that mean the time complexity of the full algorithm is the time complexity of the inner loop because the outer loop does not run any other loops .
So the time complexity will be O(Xn) where X is constant number that as we explained will realistically not exceed 100 or 200 within the numbers limits of java which will mean the total complexity of the algorithm is O(n) since we omit the constant
answered Jan 1 at 12:01
HaniHani
903317
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
add a comment |
your algorithm will run in O(n) . Let me explain why
we need to look at the inner loop to understand why it does not affect time complexity in exponential manner .
the inner loop look will run in worst case the following number of time for each iteration
1st iteration : 1/2 * N times
2nd iteration : 1/3 * N times
3rd iteration : 1/4 * N times
and so on
So the number of times the inner loop is running is decreasing each time we do it .
and we can say the total number of times the inner loop will run is
SUM(1/2 + 1/3 + 1/4 + ... 1/N)
and this is called harmonic series
https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
and although this series converge to infinity, it converge very slowly that for N of 10^43 it is less than 100
so realistically the inner loop will run in worst case constant number of N times lets say 100 times max for java float limit
So that mean the time complexity of the full algorithm is the time complexity of the inner loop because the outer loop does not run any other loops .
So the time complexity will be O(Xn) where X is constant number that as we explained will realistically not exceed 100 or 200 within the numbers limits of java which will mean the total complexity of the algorithm is O(n) since we omit the constant
answered Jan 1 at 12:01
HaniHani
903317
your algorithm will run in O(n) . Let me explain why
we need to look at the inner loop to understand why it does not affect time complexity in exponential manner .
the inner loop look will run in worst case the following number of time for each iteration
1st iteration : 1/2 * N times
2nd iteration : 1/3 * N times
3rd iteration : 1/4 * N times
and so on
So the number of times the inner loop is running is decreasing each time we do it .
and we can say the total number of times the inner loop will run is
SUM(1/2 + 1/3 + 1/4 + ... 1/N)
and this is called harmonic series
https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
and although this series converge to infinity, it converge very slowly that for N of 10^43 it is less than 100
so realistically the inner loop will run in worst case constant number of N times lets say 100 times max for java float limit
So that mean the time complexity of the full algorithm is the time complexity of the inner loop because the outer loop does not run any other loops .
So the time complexity will be O(Xn) where X is constant number that as we explained will realistically not exceed 100 or 200 within the numbers limits of java which will mean the total complexity of the algorithm is O(n) since we omit the constant
answered Jan 1 at 12:01
HaniHani
903317
answered Jan 1 at 12:01
HaniHani
903317
answered Jan 1 at 12:01
HaniHani
903317
answered Jan 1 at 12:01
HaniHani
903317
903317
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
add a comment |
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
OMG this is so GOOD!! I can fully understand your answer and it has also increased my understanding of worst case and iteration counting. Really thanks a lot!
– JJChai
Jan 1 at 20:10
add a comment |
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.
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%2f53994934%2fhow-to-count-the-runtime-of-an-algorithm-with-an-expanding-array-which-itself-i%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
