Member-only story
Big O Notation — How to Identify N Log N, Quadratic, and Cubic Algorithms
Misunderstanding Big O Notation can hurt how your systems scale.
Algorithms that increase in operation at a larger rate than linear algorithms are inefficient. This can result in systems that scale at a costly rate.
As a Software Engineer, it is vital you can identify all of the inefficient notations, and this article will cover the first three: N Log N, Quadratic and Cubic notation.
Big O Notation — How algorithms grow in complexity as the input grows in size
The Wikipedia definition of Big O Notation is — ‘In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.’
To classify these algorithms we use a growth hierarchy which is ranked in order of efficiency. A good analogy is the energy efficiency rating. Where A is the most efficient rating, and as you move down the alphabet, the lower the efficiency.
In our previous article, we covered the most efficient algorithm notations — Constant, Logarithmic and Linear. These notations grow at a small or fixed rate as the input grows.
Today our concern is the notations which grow at a larger rate than a linear increase as the input gets bigger. With a linear fixed rate, we would expect to see a fixed increase.
For example, a linear algorithm that grows by a 1-second operation time as the input increases by 1, will take 100 seconds to process an input of 100.
This is a linear algorithm, but the following notations will grow at a larger rate, as the input gets bigger:
N Log N Notation — O (n log n)
N Log N involves an algorithm that has an operation of n multiplied by log n.
