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 |