Algorithm Fundamentals
This notation describes the worst-case performance of an algorithm
What is Big O?
This ADT stores ordered, mutable collections
What is a list?
This ADT is often implemented with a hash table as the underlying data structure
What is a dictionary?
This tree structure has at most two children per node
What is a binary tree?
This search algorithm splits the list in half each time
What is binary search?
This characteristic ensures an algorithm solves the problem using reasonable resources
What is feasibility?
This ADT follows First In, First Out (FIFO)
What is a queue?
Average time complexity for searching a hash table
What is constant O(1)?
These are two common ways to represent graphs in memory
What are adjacency lists and adjacency matrices?
This iterative sorting algorithm repeatedly selects the smallest remaining element
What is selection sort?
This type of algorithm makes the best choice at each step without revisiting decisions
What is a greedy algorithm?
This ADT removes items in the reverse order they were added
What is a stack?
This issue occurs when two keys hash to the same index
What is a collision?
This traversal method uses a stack or recursion
What is depth-first search?
This sorting algorithm is stable and has a time complexity of O(n log n)
What is Merge Sort?
The time complexity of a binary search
What is logarithmic O(log n)?
This linear data structure consists of nodes with pointers to next and previous nodes
What is a doubly linked list?
This ADT stores unique, unordered elements
What is a set?
This algorithm finds the shortest path in a graph and works with negative weights
What is Bellman-Ford?
The worst-case time complexity for Quicksort
What is quadratic O(n2)?
A problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem
What is dynamic programming?
This operation removes the top item from a stack
What is pop()?
This strategy handles a collision by starting at the key's mapped bucket, and then searches subsequent buckets until an empty one is found
What is linear probing?
This data structure is best for implementing a priority queue
What is a heap?
#The time complexity of the following code block: for i in range(n): for j in range(n):
What is quadratic O(n²)?