Big O Notation

Some brief comments on computational performance.

For these examples, we will seek a specific item to ship to the customer from Tiny Warehouse.

O(1) "Order 1"

The customer needs a sample item. For samples, Tiny Warehouse ships the first item in the warehouse.

const warehouse = [1, 2, 3, 4, 5]

/* Get the first item available */
const item = warehouse[0]

Getting the first item takes 1 operation no matter how how much is stuffed in the warehouse. This is the best case possible.

"O1" means "on the order of 1 operation for all possible inputs."

O(n) "Order n"

Headquarters wants the cost of all items in Tiny Warehouse. We have all the values in an array. Calculate the sum.

/* 5 items in array */
const itemCosts = [1, 1, 3, 5, 6]
let sum = 0

/* calculate the sum */
for (let cost in itemCosts) {
  sum += cost
}
/* sum = $16 */

One operation is performed for each item in the itemCost array. Processing every item is a linear operation written as O(n) or "Order n" where n is the number of items.

O(n) calculation requires:

• 5 operations for 5 items.
• 6 operations for 6 items.
• 7 operations for 7 items.
• ...
• 100 operations for 100 items.

This loop could become costly as items are added. Look for efficiencies.

More to come...

O(N^2) "Order N Squared" or "Loops inside Loops"

To save shipping, Tiny Warehouse places orders on trucks going to the same area. A quality control step checks if any duplicates were missed.

const hasDuplicateZipcode = function (zipcodes) {
  for (let i = 0; i < zipcodes.length; i++) {
    const currentZip = zipcodes[i]

    for (let j = 0; j < zipcodes.length; j++) {
      // compare against all other destinations
      if (j !== i) {
        const anotherZip = zipcodes[j]

        // if any match, we have a duplicate!
        if (currentZip === anotherZip) {
          return true
        }
      }
    }

    // no duplicate zipcode found
    return false
  }
}

// today's order destinations
const destinationZipcodes = [98001, 98023, 98030, 98661, 98030, 98117, 98801, 98117]

// hold the shipments if we have a duplicate
let alert = hasDuplicateZipcode(destinationZipcodes)

The alert goes off since two orders going to 98117.

The alert is useless since it does not indicate which box is duplicated.

But as orders go up, so does processing time.

• 10 * 10 = 100 operations, not bad.
• 100 * 100 = 10,000 operations.
• 1,000 * 1,000 = 1,000,000 operations!
• 10,000 * 10,000 = 100,000,000 operations!!
• 100,000 * 100,000 = 10,000,000,000 operations!!!

A growing quantity of orders will greatly slow shipping.

NEXT TIME: O(Log N) or "Order Log N."

Recommended reading: The Imposter's Handbook by Rob Conery