Searching and sorting algorithms

Last Update Unknown

Search algorithms

Linear Search: The worst case scenario is that the item you are searching for is the last (nth) item in the list so the time complexity will be O (n)


Binary Search: You look at the middle item in the list until you find your item. Because the size of the list is halving on each attempt, this has a time complexity of O (log n). This is also the same for a binary tree.


Sorting algorithms

Bubble Sort: If there are n items in the list then the algorithm will make n-1 passes through the list at most; on each pass it will make n-1 comparisons giving a maximum of (n-1)(n-1) comparisons which gives a time complexity of O (n2). This means that as the list size grows bigger the Bubble Sort becomes increasingly inefficient.


Merge Sort: Divides lists into two sublists until it has n lists of 1 element. The halving process takes O (log n) operations. The sublists are then compared with adjacent sublists and ordered. This takes O (n) operations; hence the time complexity is O (n log n).