Algorithms

an assertion about the loop that is relevant to the purpose of the loop and that holds true before and after each iteration through the loop

Sequential Search is faster when the list is NOT sorted in ascending or descending order. Binary search employs the “half-half-half” method to find the target. This works best if the list is already sorted

for 2^k - 1 elements, binary search requires at most k iterations. With an array of n elements, this is log(base2)n iterations

n/2 (elements) < # iterations < n (elements)

number of required comparisons is about n^2. Iterate for k from n down to 2: find the largest among the first k elements and swap it with the kth element

number of required comparisons is about n^2. iterate for k from 2 up to n. Keep the first (k-1) elements sorted and insert the k-th element among them where it belongs

Insertion Sort, on average, requires more moves than selection sort. NEITHER, however, ALWAYS requires more moves than the other

if usually replaces while loops for recursion methods, such is the entire PURPOSE of recursion

nlogn

divide the array into two approximately equal halves; sort recursively each half, then merge them together into one sorted array

consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.[1] (Almost always slower than binary search)

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. It does NOT switch the elements.

This is the one that DOES switch the elements.

Wort number of comparisons: n^2 Best comparisons: n Average: n^2

Worse number of comparisons: n^2 Best comparisons: n^2 Average: n^2

divide and conquer (usually with recursion).

worst AND best case run time = nlogn Average = nlogn