Ω (omega)

Source board

This definition comes from the board below. Open it to see the term in context.

Complexity and Big-ODSA

More terms from this board

• amortizedcost averaged over a sequence of ops
• best/average/worst casethe input that gives least/typical/most cost
• Big-Oupper bound on growth (drop constants & lower terms)
• dominant termthe fastest-growing part (all that survives Big-O)
• in-placeuses O(1) extra space
• input-sensitivecost depends on which input, not just its size
• linearithmicn log n
• Master theoremrecurrence → complexity
• memoizationcache results to trade space for time
• the cache caveatBig-O ignores the constant, and the constant is often memory locality
• time vs space complexityops vs memory as a function of n
• Θ (theta)tight bound (matches above & below)