5 ms·

How so? https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation https://www.khanacademy.org/computing/computer-s

• loeg 8y ago
  https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. I.e., it's an asymptotic upper bound. It's also interesting to compare with Ω() (Big Omega ­— asymptotic lower bound) and Θ() (Big Theta) (big-O AND big-Omega): https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm... A good textbook on this subject is Introduction to Algorithms: https://www.amazon.com/dp/0262033844/ https://www.amazon.com/dp/0262033844/ .
  • rak00n 8y ago
    What I described is the same thing in layman's term. Worst case is the colloquial word for upper bound. And in that example n was approaching 1000. If you want to be puritan the only fault I see in my definition is instead of using a generic function I assumed it's linear function - but that's for explaining the colloquial use.
• repsilat 8y ago
  It's just an asymptotic upper bound (though often used to imply tight bounds). It's most commonly applied to worst case running time, but is often applied to expected running time ("hash table insertions run in O(1)"), space complexity, communication overhead, numerical accuracy and any number of other metrics.
  • loeg 8y ago
    Yep. Often people mean the narrower big-theta when they express complexity in terms of big-O.