Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:dikm:home [2018/01/30 04:59] – [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 77: | Line 77: | ||
| 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 87: | Line 88: | ||
| Algorithms whose most expensive step is to sort the input | Algorithms whose most expensive step is to sort the input | ||
| - | ** | + | |
| - | //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 | ||
| Also arises naturally from nested loops. | Also arises naturally from nested loops. | ||
| + | |||
| + | |||
| **//Cubic Time: //** | **//Cubic Time: //** | ||
| Line 101: | Line 105: | ||
| Finding sets which are disjoint | Finding sets which are disjoint | ||
| + | |||
| + | |||
| **//O(n^k) Time// ** | **//O(n^k) Time// ** | ||
