Big O Notation Basics for Web Developers

The TLDR — Big O Notation takes a look at how an algorithm scales.

Image for post
Source

As the size of the data set increases, how does the algorithm speed change?

The idea of Big O notation was best understood by me in story form, in 2009 a Cape Town homing pigeon called Winston, made history by beating an ISP by delivering 4GB of data 75km, in just 2 hours 6 minutes and 57 seconds, During the same time, the ADSL line had sent just 4% of the data.

Big O notation looks at the amount of time something takes verse the volume of data it has

Listed below are a different scenario

O(1)

So it takes the pigeon just as long to carry 8GB of data as it does 4GB this is known as O(1) (aka the best-case scenario). In programming terms, your project can scale and no extra completely is involved it would run as per normal, regardless of the volume (n) given it.

O(n)

On the other hand, the internet speed and the amount of data go up together, as the volume you are transferring goes up so does the amount of time it takes to complete the task. We have all experienced this at some point( big files take longer to download than little files). This is known as O(n) with the (n) as a time variable.

Thisn’ variable can be substituted for whatever you are working on, it could represent the number of users on a site, the number of requests being made to an endpoint or the amount of data being pulled from a database.

O(n²)

An example of O(n²) would be like having a loop within a loop — otherwise known as a nested loop. This scenario will lead to poor-performing algorithms as your Big O notation is going to scale quickly.

This would fall under O(n²) on the chart given above

As an example

#Data
const data = [‘A’, ‘B’, ‘C’, ‘D’]
const data2 = [1, 2, 3, 4, 5]#loopsfor (let j =0; j < data2.length; j++){ for (let i = 0; i < data.length; i++) { console.log(data[i] + data2[j])}}
#Results
A1
B1
C1
D1
A2
B2
etc...

O(n!) — Travelling Salesman Problem

The last variation of the Big O notation I would like to talk about is O(n!)

As (n) scales it becomes impractical to solve, this example is seen well in The Travelling salesman problem.

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Image for post
Source

As the number of cities or (n) variable increases, so the difficulty increases … absurdly.

At 10 cities the possible parts to consider are already at 362 880 this would bring your codebase to a standstill as your CPU would be pinned at 100% forever 😂 solving this problem.

For comparison

10 cities have 362 880 variations

if we add 6 more cities to the salesmen’s stop that 1 307 674 368 000 variations.

That has now increased the difficulty by 3.6 million times

Image for post
Source

In summary, developers need to keep their code efficient and easy to run. Big O notation can be a helpful way of doing this.

Thanks for reading this I hope it helped you understand the basics of Big O notation

LinkedIn

GitHub

Resources:

Stuff I have Learnt

Web Dev Simplified

HackerRank

I'm a Full Stack Developer 🚀 and Linux Enthusiast from Cape Town, South Africa.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store