16. Algorithms GapFill

The complexity of an algorithm, quantified using  Big OLittle EBig ELittle O notation, is a measure of how much additional resource the algorithm requires as  bus widthinput sizeline countword length increases.  In this context, that resource is either time to execute or  processor timememory spacebandwidthports required. 

An algorithm that requires no additional time, irrespective of the volume of additional data, is referred to as having  linearithmicconstantlogarithmiclinear complexity.  This would be represented as a  straight line between horizontal and verticalparabolic curvehorizontal linevertical line on a graph, expressed as  O(n)O(n!)O(1)O(2n), and an example would be  sorting an array into orderaccessing the first element in an arraycalculating a mean value from an arraycalculating a mean value from a linked list.  ConstantLinearLogarithmicLinearithmic 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 verticalcurve decreasing in gradientcurve increasing in gradientparabolic curve, expressed as  O2O(1)O(n²)O(n), and an example here is  a binary searchan insertion sorta linear searcha bubble sort.

An algorithm with  linearlinearithmicconstantlogarithmic 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  Dijkstra's algorithmbinary searcha bubble sortan insertion sort, since doubling the size of the data structure requires only one additional iteration.  The inverse of this is  exponentiallogarithmicconstantlinearithmic 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(1)O(2ⁿ)O2 complexity.