Can you figure out the Big O of this function?

@tarabyte.tech

29.5K followers · usually 14.1K views a post

Views

317.6K

Likes

13.9K

Comments

257

640

Why it worked

The video provides high-value educational content that solves a common, difficult computer science problem, establishing the creator's authority while keeping the audience engaged through a clear, step-by-step explanation.

Summary

The creator explains how to calculate the Big O complexity of a nested loop function that involves halving the loop variable. She walks through the math step-by-step to show that the total work forms a geometric series, ultimately resulting in O(N) complexity.

Structure

1Presenting the code snippet and asking for the Big O complexity
2Walking through the loop logic with n=16
3Identifying the pattern of work as a geometric series
4Generalizing the series and performing the algebraic subtraction
5Deriving the closed-form function and concluding the O(N) complexity

On-screen text

What's the Big O of this function? Can you figure out the Big O of this function? the answer actually might surprise you I'm Tara I'm a senior software engineer and I used to teach computer science at Carnegie Mellon I'm gonna give you multiple choice is it 0(n^2) is it 0(nlogn) or is it O(n) If you said 0(n) you're actually right and this one tripped me up when I first saw it so let's go through it together so i'm gonna just set n equal to 16 for this example you'll see why I chose a power of 2 later and we're gonna set i equal to N so i will also be equal to 16 in the beginning alright so we enter this outer while loop here so i again is equal to 16 here so let's go into the inner loop we have J equals 0 okay so while J is less than i and J is zero right here so J is gonna go from zero and then look we add one to it here so we're gonna go all the way up to 15 so J is gonna go from 0 to 1 5 that means this loop is gonna run a total of 16 times which means we've done like 16 units of work I'm gonna keep track of that down here actually okay now this is interesting because we have i here and we're we're having it we're dividing it by two so now when we get here i is going to be equal to eight cool so now let's fix all of this so i is equal to eight and then we go here okay so J is gonna go this time from 0 to 7 right so it's going to run eight times so this is gonna run eight times so i'm gonna add that to our total work here and then we have to divide i by two again and then we have to divide i by two again so now i is equal to four four is still greater than or equal to one we're gonna keep going okay so you can see a pattern here right let's speed through the rest :) let's divide 1 divided by 2 we're using integer division here so this is gonna be 0 actually so we get to the top here and we are done with our loop so our total work it actually looks like a geometric series and if I wanted to sort of generalize this what would that look like so i could say something like the work or W is equal to N+ and then what's this next term it's gonna be N divided by 2 and then what about the next term well it's 4 so 16 divided by 4 is 4 so n divided by 4+ n divided by 8+ finally n divided by sixteen the interesting question here is how many terms are there in this series and that actually is the same as asking the question how many times does this outer loop run well we start off at i is equal to N which is 16 in this example and we keep dividing it in half and so the number of terms that we have in our series is the number of terms that we have in our series is number of terms is equal to it's like the log base two I'm just gonna like denote that this way of N and so it's like how many times can you divide 16 by 2 before you get down to 1 is kind of what we're we're saying here okay so the more general series here and I'm just gonna name this series S is basically this right and we follow this pattern all the way until we get down to one so let me just show you something kind of nifty so if I divide both sides by two I get something that looks a little bit like that right because basically I just divide every term by two okay now bear with me but if I subtract these two from each other so if I say S minus S divided by 2 well every single one of these is going to cancel out right the only things that won't cancel out are going to be n and then at the very end minus 1/2 so that's going to be this right because n over 2 cancels n over 4 cancels all these other terms are going to cancel each other so in the end um s divided by 2 is equal to n minus 1/2 but we can just multiply by 2 here so we can say S equals two 2n minus 1 and that is the closed form function for this this summation and so this is a really tricky problem because it looks like so clearly it's like N log N maybe something I don't know if I just glanced at this and that is actually what I thought it was when I first looked at it but then when you do the actual math here the closed form is 2n minus 1 when I remove my constants from this I get it it's 0 of n and there you have it if you like these problems I'm gonna do more of them cause I think they're fun okay bye thanks for learning with me

Original caption

It's not as simple as it looks... but, we'll figure it out together :) #computerscience #learnprogramming #codingforbeginners #teaching #softwareengineer

More from @tarabyte.tech

Their other posts in the index, biggest breakout first.

Transcript

Can you figure out the Big O of this function? The answer actually might surprise you. I'm Tara, I'm a senior software engineer and I used to teach computer science at Carnegie Mellon. I'm going to give you multiple choice. Is it O(n^2)? Is it O(nlogn)? Or is it O(n)? If you said O(n) you're actually right and this one tripped me up when I first saw it, so let's go through it together. So I'm going to just set n equal to 16 for this example. You'll see why I chose a power of 2 later. And we're going to set i equal to n, so i will also be equal to 16 in the beginning. Alright, so we enter this outer while loop here. So i again is equal to 16 here. So let's go into the inner loop. We have j equals 0. Okay, so while j is less than i and j is zero right here, so j is going to go from zero and then look we add one to it here, so we're going to go all the way up to 15. So j is going to go from 0 to 15. That means this loop is going to run a total of 16 times, which means we've done like 16 units of work. I'm going to keep track of that down here actually. Okay, now this is interesting because we have i here and we're having it, we're dividing it by 2. So now when we get here i is going to be equal to 8. Cool, so now let's fix all of this. So i is equal to 8 and then we go here. Okay, so j is going to go this time from 0 to 7, right? So it's going to run 8 times. Ah, interesting. So this is going to run 8 times. So I'm going to add that to our total work here. And then we have to divide i by 2 again, so now i is equal to 4. 4 is still greater than or equal to 1, we're going to keep going. Okay, so you can see a pattern here, right? Let's speed through the rest. Let's divide 1 divided by 2, we're using integer division here, so this is going to be 0 actually. So we get to the top here and we are done with our loop. So our total work, it actually looks like a geometric series. And if I wanted to sort of generalize this, what would that look like? So I could say something like the work W is equal to N plus and then what's this next term? It's going to be N divided by 2. And then what about the next term? Well, it's 4, so 16 divided by 4 is 4, so N divided by 4 plus N divided by 8 plus finally N divided by 16. The interesting question here is how many terms are there in this series? Well, and that actually is the same as asking the question how many times does this outer loop run? Well, we start off at i is equal to N, which is 16 in this example, and we keep dividing it in half. And so the number of terms that we have in our series is number of terms is equal to it's like the log base two, I'm just going to like denote that this way of N. And so it's like how many times can you divide 16 by 2 before you get down to 1? Is kind of what we're saying here. Okay, so the more general series here, and I'm just going to name this series S, is basically this, right? And we follow this pattern all the way until we get down to 1. So let me just show you something kind of nifty. So if I divide both sides by 2, I get something that looks a little bit like that, right? Because basically I just divide every term by 2. Okay, now bear with me, but if I subtract these two from each other, so if I say S minus S divided by 2, well, every single one of these is going to cancel out, right? The only things that won't cancel out are going to be N and then at the very end minus 1/2. So that's going to be this, right? Because N over 2 cancels N over 4 cancels, all these other terms are going to cancel each other. So in the end, S divided by 2 is equal to N minus 1/2. But we can just multiply by 2 here, so we can say S equals 2N minus 1. And that is the closed form function for this, this summation. And so this is a really tricky problem because it looks like so clearly it's like N log N maybe something, I don't know, if I just glanced at this. And that is actually what I thought it was when I first looked at it. But then when you do the actual math here, the closed form is 2N minus 1. When I remove my constants from this, I get it, it's O(N). And there you have it. If you like these problems I'm going to do more of them because I think they're fun. Okay, bye, thanks for learning with me.