332 final runtimes

0.0(0)
studied byStudied by 0 people
0.0(0)
full-widthCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/10

encourage image

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)
2
New cards
Mergesort (recurrence)
Sequential: 2T(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
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)