Searching and Algorithm Analysis Flashcards
Linear Search
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
runtime
time the algorithm takes to execute
Binary Search
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).
Given an array with 32 elements, how many list elements will be checked if the key is less than all elements in the list, using binary search?
how many times you divide by 2 and add 1, to get to 1
constant time operation
operation that, for a given processor, always operates in the same amount of time, regardless of input values
Big O notation
mathematical way of describing how a function behaves in relation to the input size
Big O Notation Rules
- If f(N) 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(N) has a term that is a product of several factors, all constants (those that are not in terms of N) are omitted
Big O Notation for BinarySearch
O(log N)
Big O Notation for Linear Search
O(N)
Big O Notation for MergeSort
O(N log N)
Big O Notation for Selection Sort
O(N^2)
Big O Notation for Fibonacci
O(c^N)
worst-case runtime
runtime complexity for an input that results in the longest execution
2^20 is approximately
1 million (1,048,576)
recursive function
function that calls itself
must have a base case
Binary Search
Algorithm that searches a sorted list for a key by first comparing the key to the middle element in the list and recursively searching the half of the remaining list, so long as the key is not found.
Recurrence Relation
A function f(N) that is defined in terms of the same function operating on a value < N.
Needs to have T on both sides of the equation
