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:56] – [Chapter 3.1 Graphs- Basic Definitions and Applications:] dikm | courses:cs211:winter2018:journals:dikm:home [2018/01/30 04:59] (current) – [Chapter 2.4 - Survey of Common Running Times] dikm | ||
|---|---|---|---|
| Line 62: | Line 62: | ||
| **Summary: Goes over various common running times and common problems associated with those running times. | **Summary: Goes over various common running times and common problems associated with those running times. | ||
| - | Search space : The set of all possible solutions the search for algorithms' | + | Search space : The set of all possible solutions the search for algorithms' |
| - | Goal of Book- improving | + | One of the goals of the book is to improve |
| - | 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 | ||
| Line 178: | Line 184: | ||
| Let G be an undirected graph on n nodes. Any two of the following statements implies the third. | Let G be an undirected graph on n nodes. Any two of the following statements implies the third. | ||
| - | // | + | - G is connected |
| - | - G does not contain a cycle | + | - G does not contain a cycle |
| - | - G has n-1 edges.// | + | - G has n-1 edges. |
| // | // | ||
