Sorting Algorithms Flashcards
0
Q
Heap sort
A
Worst - O(nlogn)
Avg - O(nlogn)
Best - O(nlogn)
1
Q
Insertion sort
A
Worst - O(n^2)
Avg - O(n^2)
Best - O(n)
2
Q
Merge sort
A
Worst - O(nlogn)
Avg - O(nlogn)
Best - O(nlogn)
3
Q
Quicksort
A
Worst - O(n^2)
Avg - O(nlogn)
Best - O(nlogn)
4
Q
Quickselect
A
Worst - O(n^2)
Avg - O(n)
Best - O(n)
5
Q
Hash Table
A
Worst
- Search O(n)
- Insertion O(n)
- Deletion O(n)
Avg
- Search O(1)
- Insertion O(1)
- Deletion O(1)
6
Q
Binary Heap
A
Heapify O(n)
Find Max O(1)
Increase Key O(logn)
Insert O(logn)
Delete O(logn)
Merge O(m+n)
7
Q
Linked List (sorted)
A
Find Max O(1)
Increase Key O(n)
Insert O(n)
Delete O(1)
Merge O(m+n)
8
Q
Linked List (unsorted)
A
Find Max O(n)
Increase Key O(1)
Insert O(1)
Delete O(1)
Merge O(1)
9
Q
Theta
A
Upper and lower, tight bound
equal to
10
Q
Big O
A
Upper bound
Less than or equal to
Worst case (not always)
11
Q
Omega
A
Lower bound
Greater than or equal to
Best case (not always)
12
Q
Basic array
A
Worst & Avg.
- Indexing O(1)
- Search O(n)
