Quiz Review Flashcards
Karatsuba’s divide and conquer multiplication algorithm is faster in practice than the grade-school multipleication algorithm no matter what the size of the integers its multiples.
FALSE
Karatsuba works slower with very small numbers.
An array of 100 integers can be sorted in O(1) time.
TRUE
100 Integers is a given constant input, meaning it will always return a constant time.
Tail-Recursive Function
Uses Linear recursion
Makes a recrusive call as its very last operation
What is the selection problem? What is the name of an algorithm that solves the selection problem, and what is its average case complexity?
Find the element in an unsorted array of numbers.
Quick Select
Average Case Complexity : Linear (n)
Describe a better way to pick the pivot
- Get First, Last, and Middle element. Get Median as pivot.
- Randomly select element.
Best-Case complexity for Quicksort
T(n) = 2T(n/2) + n
O(n log n)
Worst Case Complexity for Quicksort
T(n) = T(n-1) + n
O(n^2)
If a heap is used to represent a priority queue, and the first element is
removed, the heap property is restored by moving the last element to the root
of the tree, and then running MAX-HEAPIFY on the new root element. What
is the worst-case complexity of restoring the heap property in this way?
Worst: Log(n)
Best: Constant
Describe an algorithm that takes worst-case linear time to find the 100 largest elements in an array of n elements.
- Build Max Heap
- Turn into Priority Queue
- Remove/Collect 1st 100 Largest Elements.
“In Place” Algorithm
Uses at most O(1) space beyond initial array.
“In Place “ Algorithm Examples
Heap
Insertion
Selection
“Stable” Algorithm
Does not change duplicate’s original ordering relative to each other.
“Stable” Algorithm Examples
Merge
Insertion
Timsort
“Adaptive” Algorithm
Runs faster when input is already partially or fully sorted.
“Adaptive” Algorithm Examples
Timsort
Insertion
