Big O Notation

Big 0 notation is used to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used by an algorithm.

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the imput data set.

O(N)

O(N) describes an algorithm whose performance will grow linearly and in direcr proportion to the size of the input data set. Big O NOtation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

O(N²)

O(N²) represents an algorithm whose performanxe is directly proportional to the square of the size of the input data set. This is common with algorithms that involce nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴), etc.

O(2^N)

O(2^N) denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2^N) function is exponential - startign off vert shallow, then rising meteorically.

Logarithms

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 iterationuntil the value has been found or until it can no longer split the data set.

This type of algorithm is described as O(logN). The iterative havling of data sets described in teh binary dearch 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 comlete, 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 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.

Timing

When discussing the efficiency of code, it is important to consider the readability of the code. But, it is also often important to consider the runtime of a program. For example: recursion is often considered a more elegant method in comparison to iteration. However, iteration has a much faster run time [a big O of...] than recursion. So, when deciding whether to use iteration or recursion in a section of code, one must consider the convenience, readability, and speed of the method.