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:52] – 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 160: | Line 166: | ||
| Examples/ | Examples/ | ||
| - | - Transportation Networks | + | |
| - | | + | |
| - | | + | |
| - | | + | |
| Line 175: | Line 181: | ||
| -Rooted trees help to explain the concept of hierarchy in computer science. | -Rooted trees help to explain the concept of hierarchy in computer science. | ||
| + | //Theorem 3.2: | ||
| + | |||
| + | 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 has n-1 edges. | ||
| + | // | ||
