DSA
Master theorem
recurrence → complexity
Source board
This definition comes from the board below. Open it to see the term in context.
Complexity and Big-ODSAAlso defined on Algorithm Design Patterns.
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
- 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)
- Ω (omega)lower bound