8 - Classification of Algorithms GapFill

The complexity of an algorithm, quantified using  Big ULittle UBig OLittle O notation, is a measure of how much additional resource the algorithm requires as  tree depthinput sizestack heightline count increases.  In this context, that resource is either time to execute or  hertzmemory spaceapplicationsbandwidth required. 

An algorithm that requires no additional time, irrespective of the volume of additional data, is referred to as having  polynomialconstantexponentiallinear complexity.  This would be represented as a  horizontal linecurve decreasing in gradientcurve increasing in gradientvertical line on a graph, expressed as  O(n)O(2ⁿ)O(n²)O(1), and an example would be  sorting an array into ordersearching an arraysearching a linked listaccessing the first element in an array.  ConstantQuadraticFactorialLinear complexity occurs when doubling the data to be processed doubles the time required in order to process it.  On a graph, this would be a  straight line between horizontal and verticalhorizontal lineparabolic curvevertical line, expressed as  O(n!)O(n)O(2ⁿ)O(1), and an example here is  a linear searchDijkstra's algorithma binary searchthe A* algorithm.

An algorithm with  linearithmicexponentiallogarithmicfactorial complexity is one in which doubling the data that an algorithm is required to process would increase the time required, but by less than a doubling.  An example of this type of algorithm would be  linear searchbinary searchthe A* algorithma bubble sort, since doubling the size of the data structure requires only one additional iteration.  The inverse of this is  linearlogarithmicfactorialexponential complexity.  As the data to process grows in size, so does the time (or space) required to process it, and this would curve steeply upwards on a graph.  This would be written as  O(n²)O(2ⁿ)O(n!)O(n) complexity.