Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:dikm:home [2018/01/30 04:57] – [Chapter 2.4 - Survey of Common Running Times] dikm | courses:cs211:winter2018:journals:dikm:home [2018/01/30 04:59] (current) – [Chapter 2.4 - Survey of Common Running Times] dikm | ||
|---|---|---|---|
| Line 68: | Line 68: | ||
| - | Linear Time | + | //Linear Time// |
| -At most a constant factor time the size of the input | -At most a constant factor time the size of the input | ||
| Line 78: | Line 78: | ||
| Merging Two Sorted Lists | Merging Two Sorted Lists | ||
| - | O(n logn) Time: | + | |
| + | **//O(n logn) Time: //** | ||
| Running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, | Running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, | ||
| Line 88: | Line 89: | ||
| Algorithms whose most expensive step is to sort the input | Algorithms whose most expensive step is to sort the input | ||
| - | Quadratic Time: | + | |
| + | **//Quadratic Time://** | ||
| Performing a search over all pairs of inputs and spending constant time per pair | Performing a search over all pairs of inputs and spending constant time per pair | ||
| Line 94: | Line 96: | ||
| Also arises naturally from nested loops. | Also arises naturally from nested loops. | ||
| - | Cubic Time: | + | |
| + | |||
| + | **//Cubic Time: | ||
| More elaborate sets of nested loops. | More elaborate sets of nested loops. | ||
| Line 102: | Line 106: | ||
| Finding sets which are disjoint | Finding sets which are disjoint | ||
| - | O(n^k) Time | + | |
| + | |||
| + | **//O(n^k) Time// ** | ||
| Arises for any constant k when we search over all subsets of size k | Arises for any constant k when we search over all subsets of size k | ||
