Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Next revisionBoth sides next revision |
| courses:cs211:winter2012:journals:garrett:entries:week_2 [2012/01/25 03:52] – section 2.4 garrettheath4 | courses:cs211:winter2012:journals:garrett:entries:week_2 [2012/01/25 04:14] – [Chapter 2: Basics of Algorithm Analysis] garrettheath4 |
|---|
| |
| === A Survey of Common Running Times === | === A Survey of Common Running Times === |
| Any algorithm can be characterized by its running time. There exists an ordered list of different running time complexities such that the lower order running time complexities will decrease, stay the same, or increase by very little as the problem set grows larger. Likewise, the running time complexities at the high end of the list will increase very very fast as the problem set grows larger. All of these runtime complexities are categories of Big-O complexities discussed in [[courses:cs211:winter2012:journals:garrett:entries:week_1#asymptotic_order_of_growth|Section 2.2]]. | Any algorithm can be characterized by its running time. There exists an ordered list of different running time complexities such that the lower order running time complexities will decrease, stay the same, or increase by very little as the problem set grows larger. Likewise, the running time complexities at the high end of the list will increase very very fast as the problem set grows larger. All of these runtime complexities are categories of Big-O complexities and can be expressed in terms of Big-O notation. //Big-O notation// is discussed in [[courses:cs211:winter2012:journals:garrett:entries:week_1#asymptotic_order_of_growth|Section 2.2]]. |
| | |
| | {{ :courses:cs211:winter2012:journals:garrett:entries:linear.png?|In this graph, the x axis is the problem set size and the y axis is the amount of time needed to finish the computation.}} **Linear time** problems are problems whose time complexity increases at a constant rate as the problem set grows larger. Examples of linear-time problems include finding the maximum element (such as a number) of a set and merging two sorted lists. |
| | |
| | {{ :courses:cs211:winter2012:journals:garrett:entries:growthcurves.png?400|}} **n log n time** problems are problems whose time complexity increases at a constant rate as the problem set grows larger. |
| |
| |
| ~~DISCUSSION~~ | ~~DISCUSSION~~ |
