Big O Notation — How to Identify N Log N, Quadratic, and Cubic Algorithms

Tomasz Dobrowolski
9 min readSep 7, 2022
Photo by Kevin Ku on Unsplash

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

If you are not aware of what Big O Notation is, check out the first article from the Big O Notation series — ‘What is Big O Notation?’

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.

--

--

Tomasz Dobrowolski

I break down Software Engineering and Tech concepts | Backend Engineer 🐘