Big-O Notation, Time Complexity, and What Even Google Engineers Get Wrong

you have two potential solutions to a problem solution a and solution b in local tests solution a performs extremely well outperforming solution b but as you deploy it out at massive scales you find things grinding to a halt out of desperation you deploy solution b which works smoothly what's going on here and more importantly how could you have seen this coming let's start with some examples if you have an array of unsorted items finding the index of an element means that you have to iterate through the entire list checking every single one contrast that to if the array was sorted so if the array was sorted that means that you can use something like binary search you pick the middle point compare if the value is above or below you can discard half the list and then do the same on the remaining portion intuitively without any sort of mathematical framework you can kind of see that the first has to visit every single item in the array in the absolute worst case where the item isn't in the array well with the second since you discard half the array after the first iteration and each subsequent loop progressively discards half of the remaining you only need to do a few steps more formally the first loop is big o of n or order n while the second is order log n let's understand what those mean in mathematics big o notation is a tool for helping us understand the growth of a function as x increases formally it's defined like this that is if there exists a positive real number m and a real number x sub zero such that the absolute value of f at x is less than or equal to m times g at x for all x greater than or equal to x sub 0 blah blah blah blah blah personally a lot of this page just reads like a steaming pile of math notation so let's look at some pictures instead pictures are always better here's a graph of f x so it'll just kind of do some crap here and then head up and then let's add a second function here call it g at x so what that complicated definition is saying is that if there's some point on this graph where g at x times any constant is higher than f at x and it stays higher after that then f at x is order g at x so we backtrack and here's f of x again but this time let's say that g at x is actually the function x squared so you get this curve since f of x is less than x squared around this point and after that it stays under there forever so f of x is order x squared computing big o so you have an equation like you've got 2x or 4x squared plus 7x plus three or x to the power five plus a hundred thousand it doesn't matter let's just work through a few of these so what you wanna do is select the dominant term that means you focus on the fastest growing term drop the constant and ignore pretty much everything else so f at x equals 2x is order x since x was the dominant term f of x equals 4x squared plus 7x plus 3 is order x squared and f at x equals x squared plus a hundred thousand it's order x to the power five here are some of the most common ones with examples of algorithms or code so order one that's constant time so like an array or a hash table lookup what are login that's log time or logarithmic time and an easy example is binary search order n that's linear time so that would be something like finding in an unsorted array and often radix sort like sorting instant floats is grouped in with this there's order n log n this has a bunch of different names we'll go with quasi linear anyway this is comparison sorts like merge sort and there's order n squared quadratic bubble sort comes to mind use a bigger list if you want to go through them all can't say personally run into a lot of these but they're interesting so take a look how this relates to performance in computer science when we're talking about the big o of an algorithm we're more talking about something like either the time it takes to run or the memory it uses given ever larger inputs what we're in essence doing is looking at the time or the number of steps an algorithm takes as the size of the import gets bigger going back to the first example the unsorted array you can see that as the array gets bigger the time in the worst case to search the array also gets bigger linearly in fact if the array is 10 elements long we might take 10 iterations of a loop to search the whole thing in the worst case whatever the array is a million elements long and the worst case will loop 1 million times so the growth was exactly proportional to the size of the array contrast that to binary search if we start with a small array of elements it takes just a few steps to converge to an answer in the worst case and if we were to expand that to a million elements because of the logarithmic nature of the algorithm it doesn't take that many more steps to sort through even though it's so much bigger and of course there's gotchas in the strictest terms big o describes the upper bound of an algorithm it specifically says that your function f at x won't grow faster than m times g at x for some m but that also means that something that's order n for example is also order n squared because if it doesn't grow faster than order n it definitely doesn't grow faster than n squared and so on so technically if you're one of those people you can just answer order n factorial or something like that anytime someone asks for the big o running time of an algorithm and you'll probably be right you won't like pass an interview or even be marginally useful as a co-worker but being technically correct is more important anyway here's another thing to note in software engineering we tend to use big o a bit differently that is to describe roughly how fast we expect something to run like with quicksort we often refer to it as order n log n but that's kind of the average case and it's often stated separately to have a worst case of order n squared so we kind of play a bit fast and loose with the definitions and terminology of big o when something more like big theta might make more sense so just keep that in mind so how do i use this it kind of gives you a sense of how something will scale given larger and larger inputs so if you're looking at two algorithms like the unsorted search and the sorted binary search you can kind of intuit that the unsorted search grows linearly and the other grows logarithmically and you can conclude that the binary search version will outperform the first one but there's some subtlety here this gets me to my story and what was in the title so a long long time ago i was interviewing at google past the phone screen and i was at the onsite making my way through the rounds with engineers one of the interviewers was quizzing me on subjects near the end of our interview at some point we started talking about big o analysis and i rambled a bunch on the subject gave what i thought was a decent answer and then stupidly decided to be smart and throw in some extra detail since big o is often describing the dominant term and the others are dropped when you're doing micro optimizations what's interesting is that those can actually be super important for example it's entirely possible for say an order n algorithm to outperform in order log n1 on small inputs because of those constants that aren't reflected in big o if you remember those graphs we looked at big o defines the limiting behavior as the input gets huge but at smaller values it doesn't necessarily say anything as you can guess this was a bad idea he interrupted me quickly shutting down the idea said i was just wrong on this i remember being pretty nervous and thinking okay this guy's a google engineer i looked up to these people as super smart and figured i just explained totally wrong so i gave the benefit of the doubt and replied that at huge scale like google deals with algorithmic complexity will trump everything but what i'm talking about is game optimization and small inputs it's entirely possible for those smaller terms to matter a lot he cut me off again and said that's not how it works order n is slower than log n so i tried to clarify again and said that's definitely true for larger values but at smaller values it might not be true it's possible the effects of things like caching branch prediction and he cut me off again this time he kind of snapped and said that it sounds like i don't understand big o at all this felt a little off the rails by now and unfortunately that's how the interview ended we were out of time when the next interviewer was knocking on the door so i didn't feel great about that interview ended up still getting an offer and i was at google for many years and did many interviews myself so it worked out fine definitely a low light of the process though the subtlety here is that with let's say order n versus log n as an example order log n will definitely be faster eventually as n approaches infinity look at the definition again f of x is order g at x if there exists a positive constant m and a real number x sub zero such that f of x is less than or equal to m times g at x for x greater than or equal to x sub zero and that's the important part for some x sub 0 not every single value so if the original equations were something more like 0.001 n versus a thousand log n let's just be contrived here that's order n versus order log n but if you graph those you'll notice yes of course eventually log n will be better but this whole area here this is where the asymptotically worse algorithm outperformed the supposedly faster one in a game we're not usually concerned with infinity in fact we may know for absolute certain that there's at most a thousand entities or fifty thousand particles or whatever so in those cases where we know the domain well big o doesn't necessarily tell us the whole story hope you found this useful subscribe and comment and of course if i got anything wrong let me know politely see you next time cheers

Channel: SimonDev

Views: 12,474

Rating: 4.9802141 out of 5

Keywords: simondev, game development, programming tutorial, big o notation, time complexity

Id: gCzOhZ_LUps

Length: 10min 47sec (647 seconds)

Published: Tue May 18 2021