# 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.

You have attempted of activities on this page