“Well this isn’t good,” I thought. My boss Jack was approaching me in the computer lab. It was Monday morning at 8 AM. What could it possibly be?
“Hey there Stephen! How would you like go on a work trip to Hattiesburg, Mississippi? The weather is nice and the food is great! And we really need volunteers! What do you say?”
“Damn it,” I thought. I really didn’t feel like going. These particular trips didn’t adhere to strict timelines. The expectation was one to three weeks, but things could go wrong. On one particular trip, a co-worker spent one and a half months in Yakima, Washington.
I couldn’t come up with a good excuse. “Ok. I will go,” I told Jack.
“Great! Thanks Steve!” He walked off to find another victim. I mean volunteer.
I was a cartographer inside of a Fortune 500 company. My role was processing raw imagery Our team consisted of sensor operators, a pilot, 2 cartographers, and a mechanic. Our goal: create a high-resolution, 3D map of the city and surrounding area using a small plane, a high-resolution camera and a Light Detection and Ranging (LIDAR) sensor.
We flew to Hattiesburg. Every day, the plane would fly and collect data through the high-resolution camera and LIDAR sensor. Every time we finished a given area, we were given orders to load the data on hard drives and send it back to the office in DC.
I thought this was stupid. It isn’t the 90s anymore! We aren’t using 56k modems to log into the internet. Why not use FTP or some other means of moving data through the internet?
Here’s the thing. The imagery sensors from the plane will collect hundreds of gigabytes of data. An analyst will compress the data. The compressed imagery it sent to DC, where another team looks over the data as quickly as possible. Because of the time crunch, we used FedEx to overnight our hard drives.
It was a business decision made in 2016. Yet our world isn’t a static one. Internet speeds are growing. At what point would that same team decide to use the internet to send imagery data and not FedEx a package overnight?
Enter Big O Notation.
What is Big O Notation?
In the computer science world, Big O notation classifies algorithms based on their time and space requirements. After classification, algorithms can be compared.
Let’s go back to our example. We send a package filled with hard drives from Hattiesburg, VA to Washington DC. With FedEx’s overnight shipping it will take one day. The size of my package doesn’t matter. Shipping one tiny USB stick takes one day. Shipping 100 hard drives takes one day. In Big O Notation, we would call this O(1).
O(1) indicates a constant time complexity.
Other examples of O(1):
- Accessing an array index
- Inserting a node into a linked list
- Pushing an element into an array
- Popping a stack
- Making the ill-advised choice to ride the Gravitron at your local carnival over the age of 30
Do you see the pattern? All these things have a static time variable.
Let’s get back to Hattiesburg. Our team spends $100 on FedEx’s overnight service. Our DC team gets the data.
The next day, I take a stand. I refuse to waste money on FedEx, when I could leverage the power of the internet.
At 8 PM Monday night, I begin transferring 50 gigabytes of compressed imagery data at 10 megabytes per second. It takes 12.5 hours. It completes at 8 AM, right in time for the DC team to check it out. Jack is happy.
The next day, our plane collects the same data. I decide not to use FedEx. Unfortunately, our internet slows to 8 megabytes per second. It takes 18 hours to transfer the imagery data. Our DC team doesn’t have enough time to look over the data. Jack is not happy.
There are now more variables at play. If the internet speed slows down, it takes longer to send data. If the compressed imagery data doubles to 100 gigabytes, it takes longer than a one day to complete the transfer.
In Big O Notation, we would call this O(n).
O(n) indicates Linear time complexity.
Other examples of O(n):
- Looping through an array
- Traversing a linked list
- Linear search
- Comparing two strings
- Trying to brute force your Grandmother’s password (use a computer to try every password)
Our example above illustrates a business decision influenced by Big O notation. Right now it is in the team’s best interest to stick with the static time choice of sending FedEx data overnight.
But this could change in a few years, as internet speeds grow.