At Springboard, we know how to get you a job in data science. With Springboardâ€™s Data Science Career Track, youâ€™ll master data science with a curriculum built by industry experts. Youâ€™ll work on real projects, and get 1-on-1 mentorship from a data scientist.

Computational complexity is a way to represent the amount of work required by an algorithm to solve a problem. Other complexity exists (space complexity [amount of memory required by an algorithm], complexity classes...)

Computing complexity is computed by studying how an algorithm will run over defined sets of input data, then taking the order of magnitude required for this work. (you will often find classes: O(1), O(n), O(log(n)), O(n.log(n)), O(n.m), O(n^2))

It is given as three values:

Let's take a simple algorithm (false language) explain: searching a value A through a non empty list of values X = [X1, X2, X3, ... Xn] sorted in ascending order, given A >= X1 and A <= Xn, X* are positive integers

Open in new window

This is one of the simplest search algorithms.

if we run the algorithm, we will have only one instruction run inside the loop, the first test will answer OK, so complexity will be O(1)

if we run the algorithm, we will have n iterations through the loop with 1 instruction in the loop and we will finally answer Not Found, so complexity will be => O(n)

given the amount of possible values A in the positive integer range, we have most chances of falling in the case where A is not in X, the complexity will end up as O(n)

Small optimization: using the input constraints (X sorted in ascending order), we can change the algorithm to

Open in new window

Note: since A <= Xn, I will never get out of the loop without a return, so I can remove the default case.

if we run the algorithm, we will have only one instruction run inside the loop, the first test will answer OK, so complexity will be O(1)

if we run the algorithm, we will have n iterations through the loop with 2 instructions inside and we will finally answer with Not Found, so complexity will be n iterations of 2 instructions = O(2n) = O(n); note here that complexity is an order of magnitude, not an exact number, so O(10n) is still only linked to the variable n, and will be considered equals to O(n)

given the amount of possible values A in the positive integer range, we have most chances of falling in the case where A is not in X (still), but randomness will also on average give A in the middle of the X1..Xn range, so complexity would be O(n/2) [we would do half the tests], and thus it would still be worth O(n)

Another example of complexity: a balanced binary tree search algorithm will run in O(log(n)).

So given your algorithm, identify the parts of it that depend on the amount of input data available, and simulate it running to know your complexity, and think about best, worst, and average case.

Small optimizations (limiting the number of instructions inside a loop...), though they will make a "real life" difference if you run your loop a few million times, won't change your complexity, so choosing adequate data structures and efficient algorithms to go through them is the key.

Hope this helps,

Julien