Algorithm is a step-by-step set of instructions for completing a task.
|
Linear Search: Iterate across the array from left to right, searching for a specified element.
|
Worst case O(n): the target element is the last element of the array or it doesn’t exist at all. Best case Ω(1): the target element is the first element of the array.
|
|
Binary Search: Divide and conquer, reducing the search area by half each time, trying to find a target number. First, the array should be sorted.
|
Worst case O(log n): the target element will be found at the end of the last division or it won’t be found at all. Best case Ω(1): the target element is the mid-point of the full array.
|
|
Bubble Sort: Swapping pairs of two elements: higher valued elements towards the right and the lower valued elements towards the left.
|
Worst case O(n^2): the array is in the reversed order. Best case Ω(1): the array is already perfectly sorted and we don’t need to make any swaps on the first run.
|
|
|
Selection Sort: Find the smallest unsorted element and add it to the end of the sorted list.
|
Worst case O(n2): iterate over each of the n elements of the array (to find the smallest unsorted element) → it’s at the very end of the array and repeat this proces n times, since only one element gets sorted on each pass. Best case Ω(n2): exactly the same!
|
|
|
Merge Sort: Sort smaller arrays and then merge them in sorted order.
|
The best and the worst cases are the same: n log n.
|
|
int fact(int n){if (n == 1)return 1;elsereturn n * fact(n-1);}No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.