click below
click below
Normal Size Small Size show me how
big oh
Term | Definition |
---|---|
Constant | O(1) |
Hash table lookup & modification | O(1) |
Linear | O(n) |
Iterating over a list | O(n) |
Logarithmic | O(lg n) |
Binary tree SEARCH | O(lg n) |
Divide and conquer | O(lg n) |
Action upon elements performed n-times | O(lg n) |
Time goes up linerly while n goes up exponentially | O(lg n) |
If 1s for 10-elements, 2s for 100-elements, 3s for 1000-elements? | O(lg n) |
Choice of next elements on which to perform action is one of several possibilities AND only one needs to be chosen | O(lg n) |
Finding a name in a phone book? | O(lg n) |
linearithmic | O(n log n) |
linear x logn is | O(n log n) |
Grows faster than a linear term but slower than any polynomial in n^1? | O(n log n) |
Binary tree SORT | O(n log n) |
Comparison sort, merge sort, heapsort | O(n log n) |
Polynomial | O(n^k) |
Exponential | O(2^poly(n)) |
if T(n) is upper bounded by 2poly(n), where poly(n) is some polynomial in n | O(2^poly(n)) |
Producing every subset of n-elements | O(2^poly(n)) |
Maximum matching in graphs | O(n^k) |
Cubic | O(n^3) |
Floyd and Warshall algorithm time? | O(n^3) |
Factorial | O(n!) |
Producing every ordering of every n-element | O(n!) |
f(n) = O(g(n)) means c*g(n) is | upper bound of f(n). Thus there exists some constant c such that f(n) is always ≤c*g(n), for large enough n (n≥n₀ for some constant n₀ |
f(n) = Ω(g(n)) means c*g(n) is | lower bound of f(n). Thus there exists some constant c such that f(n) is always ≥ c*g(n), for all n≥n₀ |
f(n) = Θ(g(n)) means c₁*g(n) is | upper bound of f(n) and c₂*g(n) is a lower bound on f(n) for all n≤n₀ |
prob-size n≥20 becomes useless for a __ | factorial |
prob-size n>40 becomes impractical for a __ | polynomial |
prob-size n>10,000 becomes impractical for a ___ | quadratic |
prob-size n>1,000,000,000 ok for a ___ | linear, n log n, constant |
prob-size n>400 gazillion for a __ | log n |