2 ms·
I'd love to hear more about how a quadratic sorting algorithm could be said to be O(n^3). That isn't intuitive to me.
by samwho 1y ago
I'd love to hear more about how a quadratic sorting algorithm could be said to be O(n^3). That isn't intuitive to me.
- ndriscoll 1y agoBecause |n^2|≤|n^3| as n→∞, so if |f| ≤ A|n^2| as n→∞, then |f| ≤ A|n^3| as n→∞.
- mfsch 1y agoTechnically the big O notation denotes an upper bound, i.e. it doesn’t mean “grows as fast as” but “grows at most as fast as”. This means that any algorithm that’s O(n²) is also O(n³) and O(n⁴) etc., but we usually try to give the smallest power since that’s the most useful information. The letter used for “grows as fast as” is big Theta: https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
- samwho 1y agoAhh I see, thank you!