4 ms·

I wanted to ask this question regarding big O notation. When we say f(n) = O(g(n)) all we mean to say is that f(n) <= c(g(n)) with other constraints. My questio

I wanted to ask this question regarding big O notation. When we say f(n) = O(g(n)) all we mean to say is that f(n) <= c(g(n)) with other constraints. My question is, why do we have an equal to sign, why is f(n) equal to O(g(n)).. they could have made up a new symbol to establish such a relationship... The reason why I think so is because I see equal to as a transitive relationship.. So, if a = b and c = b, then a = c .. This clearly doesnt hold when we use f(n) = O(g(n)) .. n^2 = O(n^2) and n = O(n^2), so n = n^2 which is not making any sense..

cperciva 14y ago
Writing f(n) = O(g(n)) is actually bad notation perpetuated by lazy instructors. O(g(n)) is actually a set of functions, and the correct notation is f(n) ∊ O(g(n)). (If the unicode breaks, that's the is-a-member-of symbol.)
arethuza 14y ago
I too was slightly unhappy with an equals sign being used like that, Wikipedia suggests that I was being a bit over-literal and it is considered acceptable: http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign
stonemetal 14y ago
why is f(n) equal to O(g(n)).. they could have made up a new symbol to establish such a relationship... It is an equality relationship why would they need a new symbol? f(n) = O(g(n)) .. n^2 = O(n^2) and n = O(n^2), so n = n^2 which is not making any sense You are right it doesn't make any sense. Try n^2 = O(Selection_sort(n)),O(Bubble_sort(n)) = O(Selection_sort(n)), n^2 = O(Bubble_sort(n)). Nice and transitive the way it should be.
- crntaylor 14y ago
  It's not an equality relationship. If it was an equality relationship it would be transitive. But as your parent points out, you have n=O(n^2), n^2=O(n^2) but not n=n^2, so transitivity doesn't hold. Another way to see that the relationship can't be equality: the left hand side is a function, the right hand side is a set of functions. Two things from different classes can't be equal. The relationship is simply set membership.
  - stonemetal 14y ago
    Ah thanks, I misunderstood which part was being called in to question.
- esrauch 14y ago
  Unfortunately this answer is incorrect and is a common misunderstanding of big-O. Selection sort is typically stated to be O(n^2), which is true, but the way that O works is that it's a bound from above. It means "the set of functions that asympotically are guaranteed to not take more time than". Selection sort is also O(n^3) and O(n!) and O(n^2 log log log log log n). The correct operator for saying that f(x) is O(n) is the set exists operator ∊. O(n^2) is a set of functions that is a strict subset of the set of functions that are in O(n^3). Selection sort is only big-theta(n^2), which indicates both the bounds are tight (eg for Selection sort it is true that it's asymptotic behavior is both f(n) <= an^2 + m AND f(n) >= bn^2 + n.
sesqu 14y ago
It's originally because someone once had to work with ASCII. But I believe the reason it has stuck is because it's often used in contexts like f(n)=2^O(n), which is difficult to fix elegantly. There are a couple of other notations, but they've mostly fallen by the wayside.

cperciva 14y ago

Writing f(n) = O(g(n)) is actually bad notation perpetuated by lazy instructors. O(g(n)) is actually a set of functions, and the correct notation is f(n) ∊ O(g(n)). (If the unicode breaks, that's the is-a-member-of symbol.)

arethuza 14y ago

I too was slightly unhappy with an equals sign being used like that, Wikipedia suggests that I was being a bit over-literal and it is considered acceptable: http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign

stonemetal 14y ago

why is f(n) equal to O(g(n)).. they could have made up a new symbol to establish such a relationship... It is an equality relationship why would they need a new symbol? f(n) = O(g(n)) .. n^2 = O(n^2) and n = O(n^2), so n = n^2 which is not making any sense You are right it doesn't make any sense. Try n^2 = O(Selection_sort(n)),O(Bubble_sort(n)) = O(Selection_sort(n)), n^2 = O(Bubble_sort(n)). Nice and transitive the way it should be.

crntaylor 14y ago
It's not an equality relationship. If it was an equality relationship it would be transitive. But as your parent points out, you have n=O(n^2), n^2=O(n^2) but not n=n^2, so transitivity doesn't hold. Another way to see that the relationship can't be equality: the left hand side is a function, the right hand side is a set of functions. Two things from different classes can't be equal. The relationship is simply set membership.
- stonemetal 14y ago
  Ah thanks, I misunderstood which part was being called in to question.
esrauch 14y ago
Unfortunately this answer is incorrect and is a common misunderstanding of big-O. Selection sort is typically stated to be O(n^2), which is true, but the way that O works is that it's a bound from above. It means "the set of functions that asympotically are guaranteed to not take more time than". Selection sort is also O(n^3) and O(n!) and O(n^2 log log log log log n). The correct operator for saying that f(x) is O(n) is the set exists operator ∊. O(n^2) is a set of functions that is a strict subset of the set of functions that are in O(n^3). Selection sort is only big-theta(n^2), which indicates both the bounds are tight (eg for Selection sort it is true that it's asymptotic behavior is both f(n) <= an^2 + m AND f(n) >= bn^2 + n.

sesqu 14y ago

It's originally because someone once had to work with ASCII. But I believe the reason it has stuck is because it's often used in contexts like f(n)=2^O(n), which is difficult to fix elegantly. There are a couple of other notations, but they've mostly fallen by the wayside.