3 ms·
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 ne
by 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 agoIt'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 agoAh thanks, I misunderstood which part was being called in to question.
- esrauch 14y agoUnfortunately 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.