CSE 143 Chapter Notes - Chapter 13: Analysis Of Algorithms, Selection Sort, Insertion Sort

• School: UW
• Department: Computer Science and Engineering
• Course: CSE 143
• Professor: Reges Stuart

Document Summary

Complexity is a measure of the computing resources that we used by a piece of code, such as time, memory, or disk space. One way to measure a program"s performance is to exam its code and count the number of statements that are executed. Not all statements require same amount of time to execute. When performing algorithm analysis, ignore all but the most frequently executed part of the code. Tweaking an algorithm"s code often isn"t as powerful an optimization as finding a better algorithm. An algorithm"s rate of growth, or amount by which its runtime increases as the input dataset grows, is the standard measure of the complexity of the algorithm. A complexity class is a set of algorithms that have a similar relationship between input size and resource consumption. Binary search is faster than linear search: narrows down half possibility each time. Space and time is generally a tradeoff in a program"s complexity.