Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
9 Cards in this Set
- Front
- Back
|
Merge Sort run times |
best/worst/average: all big theta n log n |
|
|
quick sort run times |
best/average: big theta n log n worst case: big theta n^2 |
|
|
bubble sort run times |
best/worst/average: big theta n^2 |
|
|
binary search run times |
best case: big theta (1) average case: big theta log n worst case: big theta log n |
|
|
insertion sort search |
best case: big theta (n) worst case: big theta n^2 average case: big theta n^2 |
|
|
Big O notation |
*represents upper bound-run time will never go over this *element to the left must be less than element to right example: n is an element of O(n^2) n^3 is NOT an element of O(n^2) |
|
|
Big Omega notation |
*represents the lower bound-run time will never go below this *element to the left must be greater than element to the right example: n^3 is an element of n^2 n is not an element of n^2 |
|
|
Big Theta notation |
*represents the tight bound-run time is equal/close to equal *elements on right and left should be equal example: n^2 + sin (n) is an element of n^2 |
|
|
Master Theorem |
T(n) = aT (n/b) + f(n) then a = b^d |
