Why Is This Algorithm Not In Polynomial Time?
$begingroup$
so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't understand what my professor meant by that even after he talked about it. When I looked at this problem I thought that is in polynomial time due the for loop iterating n times making it O(n).
The Algorithm description and Pseudocode are shown below:
A proper factor of positive integer n is a positive integer k that is
a factor of n and where 1 ≤ k < n. A positive integer n is perfect
if and only if the sum of all of the proper factors of n is equal to
n. For example, 6 is perfect because the proper factors of 6 are
1, 2 and 3, and 1 + 2 + 3 = 6.
The following algorithm determines whether positive integer n is
perfect. Is it a polynomial-time algorithm? Explain why or why
not.
isPerfect(n)
sum = 0
for i = 1, ..., n
if i is a factor of n
sum = sum + i
end if
end for
if sum == n
return true
else
return false
algorithms asymptotics computational-complexity
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
asked Dec 8 '18 at 3:07
user10762468user10762468
1
$endgroup$
add a comment |
$begingroup$
so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't understand what my professor meant by that even after he talked about it. When I looked at this problem I thought that is in polynomial time due the for loop iterating n times making it O(n).
The Algorithm description and Pseudocode are shown below:
A proper factor of positive integer n is a positive integer k that is
a factor of n and where 1 ≤ k < n. A positive integer n is perfect
if and only if the sum of all of the proper factors of n is equal to
n. For example, 6 is perfect because the proper factors of 6 are
1, 2 and 3, and 1 + 2 + 3 = 6.
The following algorithm determines whether positive integer n is
perfect. Is it a polynomial-time algorithm? Explain why or why
not.
isPerfect(n)
sum = 0
for i = 1, ..., n
if i is a factor of n
sum = sum + i
end if
end for
if sum == n
return true
else
return false
algorithms asymptotics computational-complexity
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
asked Dec 8 '18 at 3:07
user10762468user10762468
1
$endgroup$
1
$begingroup$
Complex analysis is not the same thing as complexity analysis.
$endgroup$
– Arturo Magidin
Dec 8 '18 at 3:21
$begingroup$
What's the size of your input (in bits)? How many iterations does your loop perform?
$endgroup$
– Brian Borchers
Dec 8 '18 at 3:35
add a comment |
$begingroup$
so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't understand what my professor meant by that even after he talked about it. When I looked at this problem I thought that is in polynomial time due the for loop iterating n times making it O(n).
The Algorithm description and Pseudocode are shown below:
A proper factor of positive integer n is a positive integer k that is
a factor of n and where 1 ≤ k < n. A positive integer n is perfect
if and only if the sum of all of the proper factors of n is equal to
n. For example, 6 is perfect because the proper factors of 6 are
1, 2 and 3, and 1 + 2 + 3 = 6.
The following algorithm determines whether positive integer n is
perfect. Is it a polynomial-time algorithm? Explain why or why
not.
isPerfect(n)
sum = 0
for i = 1, ..., n
if i is a factor of n
sum = sum + i
end if
end for
if sum == n
return true
else
return false
algorithms asymptotics computational-complexity
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
asked Dec 8 '18 at 3:07
user10762468user10762468
1
$endgroup$
so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't understand what my professor meant by that even after he talked about it. When I looked at this problem I thought that is in polynomial time due the for loop iterating n times making it O(n).
The Algorithm description and Pseudocode are shown below:
A proper factor of positive integer n is a positive integer k that is
a factor of n and where 1 ≤ k < n. A positive integer n is perfect
if and only if the sum of all of the proper factors of n is equal to
n. For example, 6 is perfect because the proper factors of 6 are
1, 2 and 3, and 1 + 2 + 3 = 6.
The following algorithm determines whether positive integer n is
perfect. Is it a polynomial-time algorithm? Explain why or why
not.
isPerfect(n)
sum = 0
for i = 1, ..., n
if i is a factor of n
sum = sum + i
end if
end for
if sum == n
return true
else
return false
algorithms asymptotics computational-complexity
algorithms asymptotics computational-complexity
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
asked Dec 8 '18 at 3:07
user10762468user10762468
1
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
asked Dec 8 '18 at 3:07
user10762468user10762468
1
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
edited Dec 8 '18 at 3:21
Arturo Magidin
262k34586908
262k34586908
asked Dec 8 '18 at 3:07
user10762468user10762468
1
asked Dec 8 '18 at 3:07
user10762468user10762468
1
asked Dec 8 '18 at 3:07
user10762468user10762468
1
1
1
$begingroup$
Complex analysis is not the same thing as complexity analysis.
$endgroup$
– Arturo Magidin
Dec 8 '18 at 3:21
$begingroup$
What's the size of your input (in bits)? How many iterations does your loop perform?
$endgroup$
– Brian Borchers
Dec 8 '18 at 3:35
add a comment |
1
$begingroup$
Complex analysis is not the same thing as complexity analysis.
$endgroup$
– Arturo Magidin
Dec 8 '18 at 3:21
$begingroup$
What's the size of your input (in bits)? How many iterations does your loop perform?
$endgroup$
– Brian Borchers
Dec 8 '18 at 3:35
1
1
$begingroup$
Complex analysis is not the same thing as complexity analysis.
$endgroup$
– Arturo Magidin
Dec 8 '18 at 3:21
$begingroup$
Complex analysis is not the same thing as complexity analysis.
$endgroup$
– Arturo Magidin
Dec 8 '18 at 3:21
$begingroup$
What's the size of your input (in bits)? How many iterations does your loop perform?
$endgroup$
– Brian Borchers
Dec 8 '18 at 3:35
$begingroup$
What's the size of your input (in bits)? How many iterations does your loop perform?
$endgroup$
– Brian Borchers
Dec 8 '18 at 3:35
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It’s not a polynomial time algorithm. Think what happens when you add one more bit to the input ($n$); You may end up doing twice the iterations you did before. When we say an algorithm is polynomial, it makes $text{polynomial}(x)$ calculations where $x$ is the size of the input. In this case, the size of the input is the number of bits used to describe $n$ is $log n$. The algorithm may end up doing $2^x$ iterations - not polynomial.
answered Dec 8 '18 at 3:18
mineiromineiro
812
$endgroup$
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
add a comment |
$begingroup$
The distinction to make is that the input can be represented in $k = log n$ bits. Thus, if an algorithm runs in $O(n)$ time, it really runs in $O(2^k)$ time, if we are considering the size of the input (which we usually are). So even though it runs in linear time in terms of the value of the input, it’s not necessarily polynomial time in terms of the size of the input. While we are sometimes concerned with the former, the latter is more commonly used when discussing complexity (e.g. this algorithm wouldn’t show that the language of perfect numbers is in $P$). It’s also common to refer to this former class (where runtime is polynomial in the value of the input) as “pseudo-polynomial,” rather than the stricter “polynomial.”
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3030654%2fwhy-is-this-algorithm-not-in-polynomial-time%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
$begingroup$
It’s not a polynomial time algorithm. Think what happens when you add one more bit to the input ($n$); You may end up doing twice the iterations you did before. When we say an algorithm is polynomial, it makes $text{polynomial}(x)$ calculations where $x$ is the size of the input. In this case, the size of the input is the number of bits used to describe $n$ is $log n$. The algorithm may end up doing $2^x$ iterations - not polynomial.
answered Dec 8 '18 at 3:18
mineiromineiro
812
$endgroup$
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
add a comment |
$begingroup$
It’s not a polynomial time algorithm. Think what happens when you add one more bit to the input ($n$); You may end up doing twice the iterations you did before. When we say an algorithm is polynomial, it makes $text{polynomial}(x)$ calculations where $x$ is the size of the input. In this case, the size of the input is the number of bits used to describe $n$ is $log n$. The algorithm may end up doing $2^x$ iterations - not polynomial.
answered Dec 8 '18 at 3:18
mineiromineiro
812
$endgroup$
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
add a comment |
$begingroup$
It’s not a polynomial time algorithm. Think what happens when you add one more bit to the input ($n$); You may end up doing twice the iterations you did before. When we say an algorithm is polynomial, it makes $text{polynomial}(x)$ calculations where $x$ is the size of the input. In this case, the size of the input is the number of bits used to describe $n$ is $log n$. The algorithm may end up doing $2^x$ iterations - not polynomial.
answered Dec 8 '18 at 3:18
mineiromineiro
812
$endgroup$
It’s not a polynomial time algorithm. Think what happens when you add one more bit to the input ($n$); You may end up doing twice the iterations you did before. When we say an algorithm is polynomial, it makes $text{polynomial}(x)$ calculations where $x$ is the size of the input. In this case, the size of the input is the number of bits used to describe $n$ is $log n$. The algorithm may end up doing $2^x$ iterations - not polynomial.
answered Dec 8 '18 at 3:18
mineiromineiro
812
edited Dec 9 '18 at 3:28
answered Dec 8 '18 at 3:18
mineiromineiro
812
answered Dec 8 '18 at 3:18
mineiromineiro
812
answered Dec 8 '18 at 3:18
mineiromineiro
812
812
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
add a comment |
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
+1 Good explanation, but you should learn to use Mathjax to format your posts. Start by putting dollar signs around math expressions (including numbers.)
$endgroup$
– saulspatz
Dec 8 '18 at 3:35
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
$begingroup$
Thanks for the suggestion :)
$endgroup$
– mineiro
Dec 9 '18 at 3:39
add a comment |
$begingroup$
The distinction to make is that the input can be represented in $k = log n$ bits. Thus, if an algorithm runs in $O(n)$ time, it really runs in $O(2^k)$ time, if we are considering the size of the input (which we usually are). So even though it runs in linear time in terms of the value of the input, it’s not necessarily polynomial time in terms of the size of the input. While we are sometimes concerned with the former, the latter is more commonly used when discussing complexity (e.g. this algorithm wouldn’t show that the language of perfect numbers is in $P$). It’s also common to refer to this former class (where runtime is polynomial in the value of the input) as “pseudo-polynomial,” rather than the stricter “polynomial.”
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
The distinction to make is that the input can be represented in $k = log n$ bits. Thus, if an algorithm runs in $O(n)$ time, it really runs in $O(2^k)$ time, if we are considering the size of the input (which we usually are). So even though it runs in linear time in terms of the value of the input, it’s not necessarily polynomial time in terms of the size of the input. While we are sometimes concerned with the former, the latter is more commonly used when discussing complexity (e.g. this algorithm wouldn’t show that the language of perfect numbers is in $P$). It’s also common to refer to this former class (where runtime is polynomial in the value of the input) as “pseudo-polynomial,” rather than the stricter “polynomial.”
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
The distinction to make is that the input can be represented in $k = log n$ bits. Thus, if an algorithm runs in $O(n)$ time, it really runs in $O(2^k)$ time, if we are considering the size of the input (which we usually are). So even though it runs in linear time in terms of the value of the input, it’s not necessarily polynomial time in terms of the size of the input. While we are sometimes concerned with the former, the latter is more commonly used when discussing complexity (e.g. this algorithm wouldn’t show that the language of perfect numbers is in $P$). It’s also common to refer to this former class (where runtime is polynomial in the value of the input) as “pseudo-polynomial,” rather than the stricter “polynomial.”
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
$endgroup$
The distinction to make is that the input can be represented in $k = log n$ bits. Thus, if an algorithm runs in $O(n)$ time, it really runs in $O(2^k)$ time, if we are considering the size of the input (which we usually are). So even though it runs in linear time in terms of the value of the input, it’s not necessarily polynomial time in terms of the size of the input. While we are sometimes concerned with the former, the latter is more commonly used when discussing complexity (e.g. this algorithm wouldn’t show that the language of perfect numbers is in $P$). It’s also common to refer to this former class (where runtime is polynomial in the value of the input) as “pseudo-polynomial,” rather than the stricter “polynomial.”
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
answered Dec 8 '18 at 3:26
plattyplatty
3,370320
3,370320
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3030654%2fwhy-is-this-algorithm-not-in-polynomial-time%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
1
$begingroup$
Complex analysis is not the same thing as complexity analysis.
$endgroup$
– Arturo Magidin
Dec 8 '18 at 3:21
$begingroup$
What's the size of your input (in bits)? How many iterations does your loop perform?
$endgroup$
– Brian Borchers
Dec 8 '18 at 3:35