Complexity

6 kinds

• O(1) Constant
• O(log n)  Logarithmic
• O(n)  Linear
• O(n*log n) Linear*Logarithmic
• O(n^2) Polynomial
• O(2^n) Exponential

Assignment statements and if statements that are only executed once regardless of the size of the problem are O(1).O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

• A simple “for” loop from 0 to n (with no internal loops), contributes O(n) (linear complexity);O(N)O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favors the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
• 

• A nested loop of the same type (or bounded by the first loop parameter), gives O(n^2) (quadratic complexity);O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.
• 

• Logarithmic time: given an input of size n, the number of steps it takes
• to accomplish the task are decreased by some factor with each step.

A loop in which the controlling parameter is divided by two at each step (and which terminates when it reaches 1), gives O(log n) (logarithmic complexity);


Binary search is a technique used to search sorted data sets. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.


This type of algorithm is described as O(log N). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets.

• First Merge sort uses this complexity, first we take all the data apart by splitting it. this takes Log N complexity
• We then sort it by walking through the array, this takes log N complexity. O(n) * O(log n) = O(n*log n) 

A nested loop of the same type (or bounded by the first loop parameter), gives O(n^2) (quadratic complexity);


O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.

• 
• Below or
• for for loop of n with nested for loop of n inside it; 2^n
• 
• 

• We add each time we have a new complexity for each line, but in the end only the dominant term stays when we classify the code complexity.
• Multiplication connects two different complexities and will therefr not fall off in final classification.
• Nested loops (also recursive) can cause multiplication between notations into final classicifation. (n * log n)