Wait...Is Time Complexity Like Driving from New York to Atlanta? (Not exactly)

Why we ignore “lower-order terms” in Big O Notation

So I have a friend from 100Devs who reached out to me because she’s leveling up and getting ready to start her data structures and algorithms journey via Leetcode.

She asked me to show her how to do an easy problem in Leetcode. (Easy problem in Leetcode? That’s like saying…ok I’m blanking on oxymorons right now…will come back to this).

I chose Two Sum because that’s a classic.

If you’re unfamiliar with the Two Sum problem, it’s where you are given an array of integers and target integer and you want to find the two integers whose sum equal the target but return the indexes of those numbers (not the numbers themselves).

She asked, “Could I just use a nested for loop?”

I said “Yes! You could…but…that would give you a poor time complexity with larger datasets.”

And like a good engineer, she asked “What is time complexity?”

I told her (or at least I hope I told her) “It’s the number of operations needed to complete a task with respect to the input size.”

She asked me “Is it like if I drive to Atlanta from New York, is it like if i drive straight without making any stops versus if I do make stops?”

It took me a few days but I came up with a more accurate comparison.

I sent her this message:

“I think the difference between O(n!) vs O(n^2) vs O(n) vs O(1) would be like the difference between walking vs biking vs driving vs teleporting from New York to Atlanta.”

Making stops wouldn’t make a significant difference to speed as much as the mode of transportation. You might look at making stops as coefficients or less significant operations known as lower-order operations.

Take an algorithm like that sorts and has a for loop:

function containsDuplicate(array){
    array.sort((a, b) =>  a-b)
     for(let i=0; i<array.length; i++){
          if(array[i] === array[i-1]) return true;
    }

     return false;
}

So we know that, under the hood, sorting an array gives us the time complexity of O(nlogn) (don’t ask me to explain why…yet) and a for loop with a primitive operation inside gives us time complexity of O(n). You could even say returning false is a primitive operation so that would be O(1).

We could say that the algorithm’s time complexity is O(nlogn) + O(n) + O(1) but we really don’t need to include the lower-order operations. O(nlogn) > O(n) because nlogn grows faster than n , so our time complexity or Big O notation would be O(nlogn) where n is the size of the array.

Or this algorithm with a nested loop:

function containsDuplicate(array){
    array.sort((a, b) =>  a-b)
     for(let i=0; i<array.length; i++){
          for(let j=1; j<array.length; j++){
            if(array[i] === array[j]) return true;
        }
    }
    for(let i=0; i<array.length; i++){
          if(array[i] === array[i-1]) return true;
    }

     return false;
}

We also sort here (just for example sake).

The sorting gives us time complexity of O(nlogn), the nested loop gives us a time complexity of O(n²). The loop gives us O(n) time complexity.

But we don’t estimate our time complexity to be O(nlogn) + O(n²) + O(n). We get rid of the lower-order terms because they have less influence on the overall speed of the algorithm with respect to size. O(n²) is the biggest term because it grows faster than Ologn and O(n) so our Big O notation or time complexity for this algorithm is O(n²).

So in the metaphor of travel, making stops to go to the bathroom or go shopping are more like lower-order terms in that they have less significance on the overall speed. Your actual Big O notation would be whether you drove to Atlanta versus whether you walked.

If you walked most to Atlanta from New York but then you drove back. In this case the driving would be considered the lower order term because adds significantly less time to the trip than the walk. Walking from Atlanta to New York takes 13 days whereas driving takes 12 hours. Which mode of transportation has more influence on the length of the trip? The walking. So your if we used this metaphor our Big O notation might think Walking*n + Driving*n but drop the driving so it’s Walking*n where n is the distance.

That’s my metaphor, anyway — hopefully it helps someone out there make sense of time complexity a little better. I’ve got another post brewing about how time complexity and why it matters, so stay tuned!

Please comment if you have any questions or if you have a different metaphor or any other feedback!