A visual introduction to big O notation

Summary

Big O notation is a way of describing the performance of a function without using time. Rather than timing a function from start to finish, big O describes how the time grows as the input size increases. It is used to help understand how programs will perform across a range of inputs. In this post I'm going to cover 4 frequently-used categories of big O notation: constant, logarithmic, linear, and quadratic. Don't worry if these words mean nothing to you right now. I'm going to talk about them in detail, as well as visualise them, throughout this post. Before you scroll! This post has been sponsored by the wonderful folks at ittybit, and their API for working with videos, images, and audio. If you need to store, encode, or get intelligence from the media files in your app, check them out! # Iterating Consider this JavaScript function that calculates the sum of 1 to n. function sum(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } I'm going to pass in 1 billion, written using the shorthand 1e9, so it takes a noticeable amount of time to run. Press the button below to measure how long it takes to calculate the sum of 1 to 1 billion. function sum(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } const result = sum(1e9); On my laptop this takes just under 1 second. The time you get may be different, and it may vary by a few tens of milliseconds each time you run it. This is expected. Timing code this way, by taking the start time and the end time and finding the difference, is called wall-clock time. How long do you think 2 billion, 2e9, will take? function sum(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } const result = sum(2e9); It takes about twice as long. The code loops n times and does a single addition each time. If we passed in 3 billion, we would expect the execution time to increase by a factor of three. The relationship between a function's input and how long it t...