Week 2 Flashcards
What is an Algorithm?
An algorithm is a sequence of steps for accomplishing a task
What is a Linear Search?
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 an algorithm runtime?
An algorithm’s runtime is the time the algorithm takes to execute. If each comparison takes 1 µs (1 microsecond), a linear search algorithm’s runtime is up to 1 s to search a list with 1,000,000 elements, 10 s for 10,000,000 elements, and so on. Ex: Searching Amazon’s online store, which has more than 200 million items, could require more than 3 minutes.
What is a Binary Search Algorithm?
Binary search is a faster algorithm for searching a list if the list’s elements are sorted and directly accessible (such as an array). Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).
What is Big O notation?
Big O notation is a mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size. In Big O notation, all functions that have the same growth rate (as determined by the highest order term of the function) are characterized using the same Big O notation.
What are the two rules for the Big O notation?
- If f(x) is a sum of several terms, the highest order term (the one with the fastest growth rate) is kept and others are discarded.
- If f(x) has a term that is a product of several factors, all constants (those that are not in terms of x) are omitted.
What is the Worst Case Run Time of an Algorithm?
the runtime complexity for an input that results in the longest execution.
What is Run Time Analysis?
Determines the total number of operations. Operations include assignment, addition, comparison, etc.
What is Sorting?
the process of converting a list of elements into ascending (or descending) order
What is a Selection Sort?
sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.
