Asymptotic notation and Algorithms Flashcards
List the asymptotic order from lowest to highest
- Constant O(1)
- Logarithmic (log n)
- Linear (n)
- Linear Logarithmic (nlogn)
- Quadratic (n^2)
- Polynomial (n^k)
- Exponential (2^n)
- Factorial (n!)
Name two brute force sorting algorithms
Selection Sort and Bubble sort
What is the Big O of selection sort?
Quadratic: O(n^2)
What is the big O of bubble sort?
Quadratic: O(n^2)
What is the big O of the TSP using Brute Force?
O(n!)
Name two Divide and Conquer sorting algorithms
Merge sort and quick sort
What is the big O of merge sort?
O(nlogn) - Log linear
Name two transform and conquer alogorithms
Fast Fourier Transform
AVL tree rotation
Name two decrease and conquer algorithms
Binary search
Insertion sort
What category does merge sort fall under?
Divide and Conquer
Explain the divide and conquer algorithm category
Breaks a problem into smaller, manageable subproblems.
Solves each subproblem independently.
Combines solutions of subproblems to solve the original problem.
Explain the decrease and conquer algorithm category
Reduces the problem instance’s size or complexity to solve it iteratively.
Solves a smaller instance of the same problem.
Repeats this process until reaching the base case.
Explain the transform and conquer algorithm category
Transforms the problem into a different representation, making it easier to solve.
Solves the transformed problem.
Transforms the solution back to the original problem.
Explain the greedy category
Makes the locally optimal choice at each step with the hope of finding a global optimum.
Does not reassess previous choices.
May not always result in the best overall solution.
explain the dynamic sets category
Breaks a complex problem into simpler subproblems.
Solves each subproblem just once and stores its solution in a table (memoization).
Utilizes the solutions of subproblems to solve larger instances.
