332 final runtimes
0.0(0)
Studied by 0 people
Knowt Play
Learn
Practice Test
Spaced Repetition
Match
FlashcardsCard Sorting
1/10
There's no tags or description
Looks like no tags are added yet.
Study Analytics
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
11 Terms
1
New cards
Mergesort (runtime)
split into sub-arrays
Best: O(n log n)
Avg: O(n log n)
Worst: O(n log n)
Best: O(n log n)
Avg: O(n log n)
Worst: O(n log n)
2
New cards
Mergesort (recurrence)
Sequential: 2T(N/2) + O(N)
Parallel: T(N/2) + O(N)
Parallel: T(N/2) + O(N)
3
New cards
Quicksort runtime (sequential) - worst case
O(N^2)
4
New cards
Quicksort runtime (parallel sort & parallel partition) - best case span
O(log^2N)
5
New cards
Quicksort runtime (sequential) - best case
Quicksort runtime (parallel sort & parallel partition) - worst case span
Quicksort runtime (parallel sort & parallel partition) - worst case span
O(NlogN)
6
New cards
Quicksort (recurrence) - Parallel Sort & Sequential Partition - best case span
T(N) = O(N) + T(N/2)
7
New cards
Quicksort (recurrence) - Parallel Sort & Sequential Partition - worst case span
T(N) = T(N-2) + O(N)
8
New cards
Quicksort (recurrence) - Parallel Sort & Parallel Partition - worst case span
T(N) = T(N-1) + O(logN)
9
New cards
heapsort runtime - worst/best case
nlogn
10
New cards
Insertionsort runtime - worst case
O(n^2)
11
New cards
Bucket Sort runtime - best case
O(N)
Note 
Flashcards (101)