# 6.13. Summary¶

• A sequential search is $$O(n)$$ for ordered and unordered lists.
• A binary search of an ordered list is $$O(\log n)$$ in the worst case.
• Hash tables can provide constant time searching.
• A bubble sort, a selection sort, and an insertion sort are $$O(n^{2})$$ algorithms.
• A shell sort improves on the insertion sort by sorting incremental sublists. It falls between $$O(n)$$ and $$O(n^{2})$$.
• A merge sort is $$O(n \log n)$$, but requires additional space for the merging process.
• A quick sort is $$O(n \log n)$$, but may degrade to $$O(n^{2})$$ if the split points are not near the middle of the list. It does not require additional space.
Next Section - 6.14. Key Terms