Runtimes: Algorithms and Data Structures Flashcards
1
Q
Merge Sort
A
O(n Log n ): average and worst case
2
Q
Quick Sort
A
O(n log n ): average
O(n^2): worst case
3
Q
Insertion Sort
A
O(N): best
O(N^2): worst
4
Q
Bubble Sort
A
O(N): best
O(N^2): worst
5
Q
Binary Search
A
O(Log n ): average and wort case
6
Q
Recursion requires memory, which is equal to…
A
Runtime
7
Q
Array
A
O(N)
8
Q
Dictionary / Hashtable
A
O(1) lookup
9
Q
Linked List finding first and any other node…
A
O(1) and O(N), respectively
