 or or taken why

Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account.

Don't know
Know
remaining cards
Save
0:01
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size     Small Size show me how

# big oh

TermDefinition
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
Created by: owenamends