Describe the Binary Search Linear Search Bubble Sort and Ins

Describe the Binary Search, Linear Search, Bubble Sort, and Insertion Sort in terms of Big O. Detail the worst case and average case for the each of the above algorithms or data structures.

O(1)-

O(n)-

O(n^2)-

O(log n)-

O(n log n)-

Solution

Binary Search everytime compares the middle element of the array. And if the element
you\'re searching for is less than the middle element, the right half will not be
considered for the next loop. And if the element you\'re searching for is greater than the
middle element, the left half will not be considered for the next loop. If the element is
equal to middle element the algorithm will stop. As the list becomes halved for every
iteration/recursion, the eifficiency of binary search is: O(log n.) This is how the worst
case happens. Where as the average case remains the same for this algorithm.

Linear Search will simply search the element starting from the first element in the array
till the last element. If a match occurs, the algorithm stops. So, in the worst case, the
maximum number of comparisons that could happen is n. Therefore, the worst case efficiency
is: O(n). Where as the average case remains the same for this algorithm.

BubbleSort will keep comparing the side by side elements in the array. If they are not in
ordered, they will swap positions. And once the whole array is traversed from one end to the
other, the largest element is bubbled to the right. Next the same logic continues for n-1
elements, n-2 ... and so on. So, for the number of comparisons required is:
n + (n-1) + (n-2) + ... 1. Therefore, the worst case efficiency is: O(n^2).

InsertionSort will keep comparing every element from i-1th position till 1st position with
the element in ith position. This loop continues either till the extreme left, or till the
element is less than the element at position i. Therefore, in the worst case, it will again
perform O(n^2) comparisons.