Algorithms Flashcards
Loop invariant
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 vs. Binary Search
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
Iterations for Binary Search (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
Iterations for Sequential Search
n/2 (elements) < # iterations < n (elements)
Selection Sort
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
Insertion Sort
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 vs. Selection Sort:
Insertion Sort, on average, requires more moves than selection sort. NEITHER, however, ALWAYS requires more moves than the other
While vs. if in recursion
if usually replaces while loops for recursion methods, such is the entire PURPOSE of recursion
Merge sort comparison
nlogn
Merge sort method:
divide the array into two approximately equal halves; sort recursively each half, then merge them together into one sorted array
Technique of Sequential Search:
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 Technique:
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.
Selection Sort Technique:
This is the one that DOES switch the elements.
Insertion Sort Run Times and storage complexities
Wort number of comparisons: n^2
Best comparisons: n
Average: n^2
Selection Sort Run Times and storage complexities:
Worse number of comparisons: n^2
Best comparisons: n^2
Average: n^2
