I’m using the concept of a function and an array to try and explain Big O notation in an easy to understand way (that rhymes)

Think of Big O notation in terms of how long these functions will take to complete processing. All these functions return void but they perform processing before that. These functions also take an array as the only parameter

Big O notation describes what the worse case return time will be (upper bound or the return time cannot be greater than this)

O(1) - constant return time

Return time will always be constant regardless of the size (the total count of all the elements) of the array

I’m simply printing the first element in the array and the return time will be exactly the same if the array has only one element or a million elements. This is considered constant return time

function f(array $a):void {
  print $a[0];
}

If you take a line graph with an x-y axis and plot array size on the x axis and return time on the y axis, the graph will display a horizontally straight line (not increasing)

O(n) - linear return time

Return time will be directly proportional to the size of the array (the more elements in the array, the slower the function will take to complete)

I’m iterating over the array and printing the value of each element. The iteration (the foreach loop) will take longer to reach the end of the array if there are more elements to iterate over

function f(array $a):void {
  foreach ($a as $b) {
    print $a;
  }
}

Using the x-y axis graph, the graph will display a steadily increasing straight line. Hence, being linear (no curve will be created here, O(n) is not exponential)

You would want to keep your algorithms in the region of linear return time or below if you are concerned with scaling and want to be conversative with CPU processing (if your servers are using autoscaling in the cloud, your credit card bill won’t scale too well either)

O(n2) - linear squared (quadratic) return time

Return time will directly proportional to the size of the array squared

Here I’m iterating on the same iterative foreach loop except on each interaction, I reiterate over the same array again (in other words: nested foreach loops). Don’t care about the print statement and the string concatenation here

function f(array $a):void {
  foreach ($a as $b) {
    foreach ($a as $c) {
      print $b . $c;
    }
  }
}

This is where the servers might not scale well (meaning: your app is going to need a lot more server resources in order to complete the processing)

Using the x-y axis graph, you’ll notice a curve starting to form and this would suggest exponential return time

Squared means n x n or n to the power of 2