Recursion/Unit 7
What is the base case(s)?
A data structure that is mutable, but cannot change size once created.
What is an array?
Immutable data structure; cannot change values or size after creation.
What is a tuple?
Notation to sort in reverse.
What is reverse=True?
The time complexity of linear search.
What is O(n)/linear time?
The number of times a recursive call is made before it reaches the base case.
What is recursion depth?
A data structure that is mutable and can change size after creation.
What is a list?
Function to add an element to a specific index in a list.
What is .append()?
The non destructive python sorting function.
What is sorted()?
The time complexity of binary search.
What is O(log n)?
A snapshot of the local frame and all the variables in scope.
What is a stack frame?
Function to remove an element from a list and return it.
What is .pop()?
This list operation combines two lists without modifying either original.
What is concatenation?
What is a sort key?
The time complexity of merge sort - all cases.
What is O(n log n)?
The amount of memory the algorithm needs to use.
What is space complexity?
An array in which only some of the elements have data in them.
What is a sparse array?
What it means for an object to be mutable, vs. what it means for it to be mutable.
What is being able to change the value?
What are sorted/nearly sorted sequences?
What is O(n), O(n log n), O(n^2)?
When an immutable type is passed into a function.
What is "passing by value"?
Explain the difference between an array, list, and tuple (for the purpose of this course).
List: size can change, values can change
Array: a list if it couldn't use list operations or change size
Tuple: neither size nor values (directly) can change
Explain the comparator and its use.
Defining different sorting rules than normal behaviour, comparing two given objects
Explain why insertion sort's best case is O(n).
Assumes already sorted list - no shifting needed, just goes through it.