Algorithms Flashcards
Recursion
when a function calls itself
features:
- subroutine must have a base case
- subroutine must call itself for any inputs other than base case
- subroutine must halt after a finite number of calls
Stack overflow
when the call stack pointer exceeds the stack bound - occurs when a recursive algorithm has used up all of the available memory
Big-O notation
measure of the time complexity of an algorithm
Permutation
collection of objects from a set where the order of the chosen objects matter
O(1) constant time
takes constant time to execute regardless of size of input data set
O(n) linear time
an algorithm whose performance grows in linear time
O(n^2) quadratic time
algorithm’s performance ∝ square of the size of data set
O(2^n) exponential time
time taken to execute algorithm doubles with every additional item added to data set
O (log n) logarithmic time
time taken to execute algorithm will grow very slowly as size of data set increases
O(n!) factorial time
execution time of algorithm will grow more quickly than O(2^n) (worst possible time complexity)
Linear search
involves starting from the beginning of a list and checks one item at a time to see if it is the right one
Time complexity: O(n)
Bubble sort
works by repeatedly going through a list of items, compares consecutive pairs of items and swaps the items if they are in the wrong order
Time complexity: O(n^2)
Binary search
starts at the middle of a sorted set of numbers and removes half of the data - process repeated until desired value is found or all elements have been eliminated
Time complexity: O(log n)
Binary tree search
technique for searching a binary tree that traverses the tree until the search term is found
Time complexity: O(n)
Merge sort
list is divided into the smallest unit, then each element is compared with the adjacent list to sort and merges the two adjacent lists; done until all elements are sorted and merged
Time complexity: O(nlog n)
