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.
complexity-theory
New contributor
add a comment |
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.
complexity-theory
New contributor
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
add a comment |
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.
complexity-theory
New contributor
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
complexity-theory
New contributor
New contributor
New contributor
asked 2 hours ago
Mediocre
1063
1063
New contributor
New contributor
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
add a comment |
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
add a comment |
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)$.
add a comment |
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$.
add a comment |
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.
add a comment |
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)$.
add a comment |
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)$.
add a comment |
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)$.
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)$.
answered 2 hours ago
Vincenzo
3445
3445
add a comment |
add a comment |
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$.
add a comment |
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$.
add a comment |
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$.
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$.
answered 53 mins ago
Mario Cervera
2,32411120
2,32411120
add a comment |
add a comment |
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.
add a comment |
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.
add a comment |
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.
$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.
answered 23 mins ago
leftaroundabout
85157
85157
add a comment |
add a comment |
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.
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.
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%2fcs.stackexchange.com%2fquestions%2f101324%2fo-is-not-a-function%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
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