Algorithms are systematic ways of solving certain problems.
Two categories of algorithms include searching for an item and sorting a linear sequence of values.
Algorithms for searching include sequential search and binary search
Sequential search looks for an item in a linear sequence by testing all elements one at a time, in order, until element is found or all elements of the sequence are tested.
Binary search must start with a sorted sequence. It repeatedly halves the range of elements to search by comparing the middle element with the item sought and eliminating one of the two halves. This repeats until the item is found or the search range reduces to 0.
Three algorithms for sorting include selection sort, insertion sort, and merge sort.
Selection sort repeatedly selects the next most suitable element from an unsorted partition of a linear sequence and moves it to the end of a sorted partition.
Insertion sort picks elements from an unsorted partition of a linear sequence and places them at the correct position in a sorted partition.
Merge sort works by recursively dividing a linear sequence into smaller subsequences, sorting each subsequence and merging sorted subsequences together to form a final sorted sequence.
The cost of an algorithm may be determined by a mathematical analysis called complexity analysis. This result of analysis in a mathematical expression that describes how cost grows with some respect to some input, such as the the size of the data structure being processed (\(N\)).
Complexity analysis typically looks at cost in terms of the time it takes to complete the execution of an algorithm (time complexity) or the amount of memory required (space complexity).
Complexity classes categorize growth rate as a function of the problems size (\(N\)). Common complexity classes are listed in Table 13.1.2. The order of these classes is important in order to be able to compare algorithms.
Complexity analysis typically derives one or more of three measures: worst-case complexity (\(O(…)\) notation), best-case complexity (\(\Omega(…)\) notation), and average-case complexity (\(\Theta(…)\) notation). Worst-case complexity tends to be the most interesting of the three because it reports a theoretical upper bound of how resource requirements grow with problem size.
