Why aren't primary tests easily linear in time complexity?












1














Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear.
I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation. But why would we do so?
It seems to me wrong. The growth in calculation should be calculated compared to the number itself. Why do we compare it to the binary representation?










share|cite|improve this question



























    1














    Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear.
    I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation. But why would we do so?
    It seems to me wrong. The growth in calculation should be calculated compared to the number itself. Why do we compare it to the binary representation?










    share|cite|improve this question

























      1












      1








      1







      Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear.
      I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation. But why would we do so?
      It seems to me wrong. The growth in calculation should be calculated compared to the number itself. Why do we compare it to the binary representation?










      share|cite|improve this question













      Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear.
      I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation. But why would we do so?
      It seems to me wrong. The growth in calculation should be calculated compared to the number itself. Why do we compare it to the binary representation?







      algorithm-analysis time-complexity runtime-analysis






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 3 hours ago









      bilanush

      193




      193






















          1 Answer
          1






          active

          oldest

          votes


















          3














          Simple. When you give the number one trillion as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?



          And by all means, you are free to choose whichever representation you feel comfortable with.



          We analyze the runtime as a function of the size of the input, not as the magnitude of the number represented by the input were the input to be a number.






          share|cite|improve this answer





















          • Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
            – bilanush
            19 mins ago












          • We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
            – bilanush
            10 mins ago










          • @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
            – hobbs
            3 mins ago











          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: "419"
          };
          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: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102099%2fwhy-arent-primary-tests-easily-linear-in-time-complexity%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









          3














          Simple. When you give the number one trillion as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?



          And by all means, you are free to choose whichever representation you feel comfortable with.



          We analyze the runtime as a function of the size of the input, not as the magnitude of the number represented by the input were the input to be a number.






          share|cite|improve this answer





















          • Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
            – bilanush
            19 mins ago












          • We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
            – bilanush
            10 mins ago










          • @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
            – hobbs
            3 mins ago
















          3














          Simple. When you give the number one trillion as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?



          And by all means, you are free to choose whichever representation you feel comfortable with.



          We analyze the runtime as a function of the size of the input, not as the magnitude of the number represented by the input were the input to be a number.






          share|cite|improve this answer





















          • Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
            – bilanush
            19 mins ago












          • We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
            – bilanush
            10 mins ago










          • @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
            – hobbs
            3 mins ago














          3












          3








          3






          Simple. When you give the number one trillion as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?



          And by all means, you are free to choose whichever representation you feel comfortable with.



          We analyze the runtime as a function of the size of the input, not as the magnitude of the number represented by the input were the input to be a number.






          share|cite|improve this answer












          Simple. When you give the number one trillion as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?



          And by all means, you are free to choose whichever representation you feel comfortable with.



          We analyze the runtime as a function of the size of the input, not as the magnitude of the number represented by the input were the input to be a number.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 2 hours ago









          Pål GD

          5,8871939




          5,8871939












          • Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
            – bilanush
            19 mins ago












          • We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
            – bilanush
            10 mins ago










          • @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
            – hobbs
            3 mins ago


















          • Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
            – bilanush
            19 mins ago












          • We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
            – bilanush
            10 mins ago










          • @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
            – hobbs
            3 mins ago
















          Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
          – bilanush
          19 mins ago






          Sorry. But this is exactly what I don't understand. Why do we care about the binary representation ? It just looks like a manipulation of looking at it's binaric input and asking about the complexity of it. Why don't you look at the number itself which is what we truly care about. The whole point of complexity is to assess how fast the time grows as we move to greater numbers. So the most logical way of looking at it is by assessing how fast for example grow when we move from 10 to 100 . So it's 2^4 compared to 2^7 the growth is exactly linearly proportional to the input number
          – bilanush
          19 mins ago














          We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
          – bilanush
          10 mins ago




          We as humans deal with the number itself. Not with it's binaric shape. Why on Earth would it matter the complexity compared to binaric input? We are only trying to figure out how complicated the algorithm gets as we go to greater numbers. It doesn't matter at all the way computer choose to write it. Buttom line we should care only about the number of operations the computer does, and as well as the input. But of course, we should care about the magnitude of the number because this is what we are having in our heads , what is the rate in which the complexity grows as we go to great number
          – bilanush
          10 mins ago












          @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
          – hobbs
          3 mins ago




          @bilanush no, we as humans are incapable of doing math on "the number itself". Usually we use the base-10 representation. Which is the same size as the base-2 representation, within a constant factor.
          – hobbs
          3 mins ago


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Computer Science 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.





          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%2fcs.stackexchange.com%2fquestions%2f102099%2fwhy-arent-primary-tests-easily-linear-in-time-complexity%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

          數位音樂下載

          When can things happen in Etherscan, such as the picture below?

          格利澤436b