2.3 Algorithms

starts from the calculated . If the item at the midpoint is the item to be found it . If the item is not found, of the data set that cannot contain the item is discarded. Repeats until the data item is found or no items are left to check the data set must be first. Time efficiency of O log n which. Scales very well.

starts from the item in the data set. Each item of data is checked one at a time until the item is or the end of the data set is reached. The data set does not need to be sorted first. Time of O n. Does not scales as well as binary search.

Each pair of items in the data set are compared. If the two items are in the wrong order they are . The algorithm until no swaps are made. Time complexity of O n^2 (Polynomial).

Partitions the data into sorted and . The correct position of an item is found by comparing each item in the unsorted partition to all the other items in the sorted partition. All the items at the insertion position and above are up by one position.

step: the data set is split into lists of 1 item merge step: items in two adjacent lists are combined to create one new list maintaining the correct order of items as they are added merge step: the algorithm merging lists until only one sorted list remains. Linearithmic (O n log n)

Choose a . Compare each element to the pivot… Put items < pivot in the left sublist ... Put items > pivot in the right sublist. Choose a pivot in each sublist And until all sublists are sorted. Linearithmic) O n log n). Divide and Conquer.

Finds the path between two nodes on a graph. Uses a value to optimise performance.

Describes the time or complexity of an algorithm. How the algorithm will perform as the data set gets bigger. O1, On, On^2, O2^n, Log N, N log N

An algorithm used on a . To find the path between a start node and all other nodes.

Constant. The time needed to perform an algorithm remains constant as the data set . No memory space needed.

Linear. The time needed to perform an algorithm at the same as the size of the data set. The amount of memory required increases at the same rate as the size of the data set.

Logarithmic. The time needed to perform an algorithm increases at a rate as the data set grows, because the algorithm repeatedly the data size.

Polynomial. The time needed to perform an algorithm grows at a rate as the data set increases, usually because it involves loops. The amount of extra memory required grows quadratically as the data set increases, usually because uses a n x m matrix structure.

Exponential. The time needed to perform an algorithm with each additional in the input. The amount of extra memory required doubles with every additional input element.

Used in A* algorithm. An of how close a node is to the providing a guided “best guess” of the remaining cost so the search explores the most promising paths first.