**Ask a monkey a physics question thread**

[OngBonga]

What the fuck are you people talking about?

[MadMojoMonkey]

What the fuck are you people talking about?

Big-O notation is fundamentally important to computer programming.

A common request for a computer might be to sort a list of numbers in ascending order.
There are many ways it could do this. Each way will take a different number of processes to complete.
The number of processes is a function of the size of the data set, N, and the algorithm.

This is where we want to compare algorithms and determine which is fastest. We run into a problem, though.
All of the methods are also heavily sensitive to the initial sorting of the list.
If only 1 number is out of place out of the list, then it will (in general) take less time to sort than if the numbers in the list are randomized.
Some methods will be faster at sorting certain arrangements within the list, but slower at others.

We want to pick the best (fastest) algorithm, on average.
So we want to talk about the EV of the runtime of the algorithm. We do this by calculating the EV of the number of process steps the algorithm needs to sort any list of size N.

We class the algorithms using Big-O notation.
If an algorithm is expected to take N steps for each element in the list of size N, then we say the algorithm has Big-O of n-squared
O( N^2 )
If there was another algorithm is expected to take log(N) steps for each element in the list, then we say it has
O( N*log(N) )
Big-O of N-log-N. This is much faster, and hard to beat for most common tasks, like sorting.

E.g.
If N = 10
The O( N^2 ) algorithm is expected to take ( 10^2 = ) 100 process steps to complete.
The O( N*log(N) ) algorithm is expected to take ( 10*(1) = ) 10 process steps to complete.

If N = 100
The O( N^2 ) algorithm is expected to take ( 100^2 = ) 10,000 process steps to complete.
The O( N*log(N) ) algorithm is expected to take ( 100*(2) = ) 200 process steps to complete.

***
So Big-O notation is a way of broadly describing the speed of a computational algorithm by finding the EV of the number of steps the program will take to run to completion.

This system of notation also helps to optimize the architecture and design of printed circuits. An algorithm can be hard coded, E.g. into the adder within an ALU. Now the algorithm is permanent on that chip, and designing it to be as fast as economically possible is ideal.