Midterm Flashcards
1
Q
For loop
A
O(n)
2
Q
Addition/subtraction
A
O(1)
3
Q
Array List
A
- Find an element in an array - O(n)
- Find kth element - c
- insertion and deletion (Worst Case) - O(n)
- repeated insertion (Worst Case) - O(n^2)
4
Q
Linked List
A
- Find an element - O(n)
- Find kth element - O(n)
- insertion and deletion - c
5
Q
Binary Search Tree
A
- O(log n)
- Find (Worst Case) - O(log N)
- Insert and remove - O(n)
- Worst case - O(n)
- BST printing - O(n)
6
Q
AVL Tree
A
- Find - O(log n)
- Insert and delete - O(log n)
- Print - O(n)
7
Q
B-Tree
A
O(log n)
8
Q
Priority Queues
A
- Linked Lists
- insert in front - O(1)
- deleteMin - O(n)
- Sorted Linked Lists
- insertion - o(n)
- deleteMin - O(1)
- BST
- Insert/delete - O(log n)
9
Q
Binary Heap
A
- O(n)
- Worst case O(n log n)
10
Q
d-Heap
A
- insert - O(logd n)
- deleteMin O(d logd n)
11
Q
Min-max Heap
A
- Insert/delete - O(log n)
12
Q
Insertion Sort
A
- Average - O(n)
- Worst - O(n^2)
13
Q
Heapsort
A
- O(n log n)
14
Q
Merge Sort
A
- O(n log n)
15
Q
Quick Sort
A
- Average - O(n log n)
- Worst - O(n^2)
16
Q
Radix Sort
A
- Best: O(n)
- Worst O(n^2)
17
Q
Topological ordering algorithm
A
O(n^2)
O(|E| + |V|)
18
Q
Dijkstra’s Algorithm
A
O(N^2 + |E|)
19
Q
Ford-Fulkerson’s Algorithms
A
O(C|E|)
20
Q
Minimum spanning tree
- Kruskal’s algorithm
- Prim’s algorithm
A
O(E log V)
O(V^2)
21
Q
Breadth-First Search
Depth-First Search
A
O(V + E)
22
Q
A
