Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

5.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 quicksort 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.