Algorithms Flashcards
What is an algorithm?
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.
How is Algorithm efficiency typically measured?
Algorithm efficiency is typically measured by the algorithm’s computational complexity.
What is Computational complexity?
Computational complexity is the amount of resources used by the algorithm.
What is runtime complexity?
An algorithm’s runtime complexity is a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.
What is an algorithm’s worst case?
An algorithm’s worst case is the scenario where the algorithm does the maximum possible number of operations.
What is an algorithm’s best case?
An algorithm’s best case is the scenario where the algorithm does the minimum possible number of operations.
Describe what a Linear search algorithm does.
Linear search is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.
What is algorithm runtime?
An algorithm’s runtime is the time the algorithm takes to execute.
What is Big O notation?
Big O notation is a mathematical way of describing how a function (running time, or runtime, of an algorithm) behaves in relation to the input size.
What is the worst-case runtime?
The worst-case runtime of an algorithm is the runtime complexity for an input that results in the longest execution.
What is the selection sort algorithm?
Selection sort is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.
What is the Insertion sort algorithm?
Insertion sort is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.
What is the Quicksort algorithm?
Quicksort is a sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted), and then recursively sorts each of those parts.
What is the Merge sort algorithm?
Merge sort is a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list.
What is Shell sort algorithm?
Shell sort is a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm.
