O(.) is not a function











up vote
1
down vote

favorite












I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.



I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.



$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.










share|cite|improve this question







New contributor




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
















  • 3




    $mathcal{O}(f(n))$ is a set represneted by $f(n)$. Normally, one should write $T(n) in mathcal{O}(f(n))$.
    – kelalaka
    2 hours ago












  • I would argue that $mathcal{O}$ is a function. But rightly so it does not spit out a number, it spits out a set of functions.
    – Samy Bencherif
    34 mins ago















up vote
1
down vote

favorite












I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.



I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.



$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.










share|cite|improve this question







New contributor




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
















  • 3




    $mathcal{O}(f(n))$ is a set represneted by $f(n)$. Normally, one should write $T(n) in mathcal{O}(f(n))$.
    – kelalaka
    2 hours ago












  • I would argue that $mathcal{O}$ is a function. But rightly so it does not spit out a number, it spits out a set of functions.
    – Samy Bencherif
    34 mins ago













up vote
1
down vote

favorite









up vote
1
down vote

favorite











I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.



I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.



$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.










share|cite|improve this question







New contributor




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











I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.



I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.



$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.







complexity-theory






share|cite|improve this question







New contributor




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











share|cite|improve this question







New contributor




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









share|cite|improve this question




share|cite|improve this question






New contributor




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









asked 2 hours ago









Mediocre

1063




1063




New contributor




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





New contributor





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






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








  • 3




    $mathcal{O}(f(n))$ is a set represneted by $f(n)$. Normally, one should write $T(n) in mathcal{O}(f(n))$.
    – kelalaka
    2 hours ago












  • I would argue that $mathcal{O}$ is a function. But rightly so it does not spit out a number, it spits out a set of functions.
    – Samy Bencherif
    34 mins ago














  • 3




    $mathcal{O}(f(n))$ is a set represneted by $f(n)$. Normally, one should write $T(n) in mathcal{O}(f(n))$.
    – kelalaka
    2 hours ago












  • I would argue that $mathcal{O}$ is a function. But rightly so it does not spit out a number, it spits out a set of functions.
    – Samy Bencherif
    34 mins ago








3




3




$mathcal{O}(f(n))$ is a set represneted by $f(n)$. Normally, one should write $T(n) in mathcal{O}(f(n))$.
– kelalaka
2 hours ago






$mathcal{O}(f(n))$ is a set represneted by $f(n)$. Normally, one should write $T(n) in mathcal{O}(f(n))$.
– kelalaka
2 hours ago














I would argue that $mathcal{O}$ is a function. But rightly so it does not spit out a number, it spits out a set of functions.
– Samy Bencherif
34 mins ago




I would argue that $mathcal{O}$ is a function. But rightly so it does not spit out a number, it spits out a set of functions.
– Samy Bencherif
34 mins ago










3 Answers
3






active

oldest

votes

















up vote
2
down vote













Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a simplified way to write that $T(n) in O(f(n))$.



Note that this also clarifies some issues of the $O$ notation as it is normally used.
For example, $n^2 in O(n^3)$ but $n^3 notin O(n^2)$. So you can write $n^2 = O(n^3)$, but you cannot write $n^3 = O(n^2)$.






share|cite|improve this answer




























    up vote
    0
    down vote













    Just as a small contribution ... In The Algorithm Design Manual book, you can find a paragraph about this issue:




    The Big $O$ notation provides for a rough notion of equality when comparing
    functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its
    meaning can always be resolved by going back to the definitions in terms of upper
    and lower bounds. It is perhaps most instructive to read the " = " here as meaning
    "one of the functions that are". Clearly, $n^2$ is one of functions that are $O(n^3)$.




    This is in line with Vincenzo's answer: you should simply interpret $O(f(n))$ as a set of functions and the = symbol as a set membership symbol $in$.






    share|cite|improve this answer




























      up vote
      0
      down vote













      $O$ is a function
      $$begin{align}
      O : (mathbb{N}to mathbb{R}) &to mathbf{P}(mathbb{N}to mathbb{R})
      \ f &mapsto O(f)
      end{align}$$

      i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic behaviour of $f$. And strictly speaking the correct notation is thus
      $$
      (n mapsto T(n)) in O(nmapsto f(n))
      $$

      or short
      $$
      T in O(f)
      $$

      but it's customary in maths, science and CS to just use a variable somewhere in the expression to denote that you're considering functions of the argument $n$ on both sides. So $T(n) in O(f(n))$ is quite fine as well. $T(n) = O(f(n))$ is pretty much wrong though, as you suspected.






      share|cite|improve this answer





















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


        }
        });






        Mediocre 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%2fcs.stackexchange.com%2fquestions%2f101324%2fo-is-not-a-function%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes








        up vote
        2
        down vote













        Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a simplified way to write that $T(n) in O(f(n))$.



        Note that this also clarifies some issues of the $O$ notation as it is normally used.
        For example, $n^2 in O(n^3)$ but $n^3 notin O(n^2)$. So you can write $n^2 = O(n^3)$, but you cannot write $n^3 = O(n^2)$.






        share|cite|improve this answer

























          up vote
          2
          down vote













          Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a simplified way to write that $T(n) in O(f(n))$.



          Note that this also clarifies some issues of the $O$ notation as it is normally used.
          For example, $n^2 in O(n^3)$ but $n^3 notin O(n^2)$. So you can write $n^2 = O(n^3)$, but you cannot write $n^3 = O(n^2)$.






          share|cite|improve this answer























            up vote
            2
            down vote










            up vote
            2
            down vote









            Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a simplified way to write that $T(n) in O(f(n))$.



            Note that this also clarifies some issues of the $O$ notation as it is normally used.
            For example, $n^2 in O(n^3)$ but $n^3 notin O(n^2)$. So you can write $n^2 = O(n^3)$, but you cannot write $n^3 = O(n^2)$.






            share|cite|improve this answer












            Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a simplified way to write that $T(n) in O(f(n))$.



            Note that this also clarifies some issues of the $O$ notation as it is normally used.
            For example, $n^2 in O(n^3)$ but $n^3 notin O(n^2)$. So you can write $n^2 = O(n^3)$, but you cannot write $n^3 = O(n^2)$.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered 2 hours ago









            Vincenzo

            3445




            3445






















                up vote
                0
                down vote













                Just as a small contribution ... In The Algorithm Design Manual book, you can find a paragraph about this issue:




                The Big $O$ notation provides for a rough notion of equality when comparing
                functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its
                meaning can always be resolved by going back to the definitions in terms of upper
                and lower bounds. It is perhaps most instructive to read the " = " here as meaning
                "one of the functions that are". Clearly, $n^2$ is one of functions that are $O(n^3)$.




                This is in line with Vincenzo's answer: you should simply interpret $O(f(n))$ as a set of functions and the = symbol as a set membership symbol $in$.






                share|cite|improve this answer

























                  up vote
                  0
                  down vote













                  Just as a small contribution ... In The Algorithm Design Manual book, you can find a paragraph about this issue:




                  The Big $O$ notation provides for a rough notion of equality when comparing
                  functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its
                  meaning can always be resolved by going back to the definitions in terms of upper
                  and lower bounds. It is perhaps most instructive to read the " = " here as meaning
                  "one of the functions that are". Clearly, $n^2$ is one of functions that are $O(n^3)$.




                  This is in line with Vincenzo's answer: you should simply interpret $O(f(n))$ as a set of functions and the = symbol as a set membership symbol $in$.






                  share|cite|improve this answer























                    up vote
                    0
                    down vote










                    up vote
                    0
                    down vote









                    Just as a small contribution ... In The Algorithm Design Manual book, you can find a paragraph about this issue:




                    The Big $O$ notation provides for a rough notion of equality when comparing
                    functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its
                    meaning can always be resolved by going back to the definitions in terms of upper
                    and lower bounds. It is perhaps most instructive to read the " = " here as meaning
                    "one of the functions that are". Clearly, $n^2$ is one of functions that are $O(n^3)$.




                    This is in line with Vincenzo's answer: you should simply interpret $O(f(n))$ as a set of functions and the = symbol as a set membership symbol $in$.






                    share|cite|improve this answer












                    Just as a small contribution ... In The Algorithm Design Manual book, you can find a paragraph about this issue:




                    The Big $O$ notation provides for a rough notion of equality when comparing
                    functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its
                    meaning can always be resolved by going back to the definitions in terms of upper
                    and lower bounds. It is perhaps most instructive to read the " = " here as meaning
                    "one of the functions that are". Clearly, $n^2$ is one of functions that are $O(n^3)$.




                    This is in line with Vincenzo's answer: you should simply interpret $O(f(n))$ as a set of functions and the = symbol as a set membership symbol $in$.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 53 mins ago









                    Mario Cervera

                    2,32411120




                    2,32411120






















                        up vote
                        0
                        down vote













                        $O$ is a function
                        $$begin{align}
                        O : (mathbb{N}to mathbb{R}) &to mathbf{P}(mathbb{N}to mathbb{R})
                        \ f &mapsto O(f)
                        end{align}$$

                        i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic behaviour of $f$. And strictly speaking the correct notation is thus
                        $$
                        (n mapsto T(n)) in O(nmapsto f(n))
                        $$

                        or short
                        $$
                        T in O(f)
                        $$

                        but it's customary in maths, science and CS to just use a variable somewhere in the expression to denote that you're considering functions of the argument $n$ on both sides. So $T(n) in O(f(n))$ is quite fine as well. $T(n) = O(f(n))$ is pretty much wrong though, as you suspected.






                        share|cite|improve this answer

























                          up vote
                          0
                          down vote













                          $O$ is a function
                          $$begin{align}
                          O : (mathbb{N}to mathbb{R}) &to mathbf{P}(mathbb{N}to mathbb{R})
                          \ f &mapsto O(f)
                          end{align}$$

                          i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic behaviour of $f$. And strictly speaking the correct notation is thus
                          $$
                          (n mapsto T(n)) in O(nmapsto f(n))
                          $$

                          or short
                          $$
                          T in O(f)
                          $$

                          but it's customary in maths, science and CS to just use a variable somewhere in the expression to denote that you're considering functions of the argument $n$ on both sides. So $T(n) in O(f(n))$ is quite fine as well. $T(n) = O(f(n))$ is pretty much wrong though, as you suspected.






                          share|cite|improve this answer























                            up vote
                            0
                            down vote










                            up vote
                            0
                            down vote









                            $O$ is a function
                            $$begin{align}
                            O : (mathbb{N}to mathbb{R}) &to mathbf{P}(mathbb{N}to mathbb{R})
                            \ f &mapsto O(f)
                            end{align}$$

                            i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic behaviour of $f$. And strictly speaking the correct notation is thus
                            $$
                            (n mapsto T(n)) in O(nmapsto f(n))
                            $$

                            or short
                            $$
                            T in O(f)
                            $$

                            but it's customary in maths, science and CS to just use a variable somewhere in the expression to denote that you're considering functions of the argument $n$ on both sides. So $T(n) in O(f(n))$ is quite fine as well. $T(n) = O(f(n))$ is pretty much wrong though, as you suspected.






                            share|cite|improve this answer












                            $O$ is a function
                            $$begin{align}
                            O : (mathbb{N}to mathbb{R}) &to mathbf{P}(mathbb{N}to mathbb{R})
                            \ f &mapsto O(f)
                            end{align}$$

                            i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic behaviour of $f$. And strictly speaking the correct notation is thus
                            $$
                            (n mapsto T(n)) in O(nmapsto f(n))
                            $$

                            or short
                            $$
                            T in O(f)
                            $$

                            but it's customary in maths, science and CS to just use a variable somewhere in the expression to denote that you're considering functions of the argument $n$ on both sides. So $T(n) in O(f(n))$ is quite fine as well. $T(n) = O(f(n))$ is pretty much wrong though, as you suspected.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered 23 mins ago









                            leftaroundabout

                            85157




                            85157






















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










                                draft saved

                                draft discarded


















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













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












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
















                                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%2f101324%2fo-is-not-a-function%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

                                What visual should I use to simply compare current year value vs last year in Power BI desktop

                                Alexandru Averescu

                                Trompette piccolo