In the previous video, we looked at two pieces of code that took radically different amounts of time to compute the same result. We concluded that performance is affected by the number of operations our code performs -- but that it's how quickly the number of operations grows that is important, rather than a precise count of the number of operations performed for any given input size. Let's explore that idea further.
Here's our first function from the last video. For each element in the array, it assigns the elementâ€™s position as its value. We saw that this code performed n assignment operations each time it was called -- one for each element in the array.
Here's a new piece of code that does exactly the same thing. Take a second to convince yourself. It's a little silly, but it assigns roughly half of the index to the element in the first loop and then the other half in the second loop.
So the question is: how much worse is our new function? It's clearly harder to read -- and that makes it worse, just by itself -- but how much worse is it in terms of performance?
This loop performs n assignments.
And this loop also performs n assignments. So that's a total of 2 * n assignment statements. We can estimate that this function will take twice as much time to run.
But that's not quite right. It looks like it takes roughly 2.5 or 3 times as long.
The runtimes grow as we expect.
If we double the size of the input, this function takes twice as long.
And so does this one.
But it still takes more than twice as long for the second version to run. Why wasn't our estimate correct?
We're not just doing an assignment statement, right? There's more to it. We're doing more math in the new function. Does this mean that we should be counting math operations in addition to assignments? There *are* more of them ...
No math operations here. So I'll just count assignments. There's just one. So that's n operations over the entire loop.
One math operation and one assignment. So that's 2 * n operations.
And three more operations and one assignment. So that's 4 * n operations, for a total of 6 * n operations.
But it didn't take *six* times as long. Maybe we should also count the instructions in the loop?
Stop. Is this important? Do we need to be that precise?
Our numbers are all over the place. As we noted in the last video, there are many things that contribute to the runtime of a program. We *can't* be precise. And that leads us to an interesting point.
Recall that we only care about runtime performance when our inputs are big: if the inputs are small, the code will run so fast we won't even notice it. So if the inputs are big, then
the size of the input is going to be much larger than some arbitrary constant. It doesn't really matter if we count 3 operations in the loop or 6.
The point is that for any large input we care about n and 6n are much closer to each other than they are to n squared. *We can ignore the constant.* To repeat what we said earlier, what's important isn't precisely how many instructions will be executed, but how quickly the number of operations *grows*.
Here's another example. This code runs a loop that repeats 1 million times.
It's pretty slow, right? Linear is much faster.
But if the input is big enough, linear becomes worse. It's not about the constant factor: it's how quickly the number of operations grows. Or in this case, the fact that the number of operations *doesn't* grow for our constant function.
These ideas lead to a concept called *asymptotic complexity*,
which we represent using Big-O notation.
The notation has a mathematical basis, and if you study computer science theory, you'll spend time calculating the complexity of functions and proving bounds on them.
But our goal is simply give you a tool for evaluating the runtime of your functions. We would say that the function constant is
big-o of 1. And our two functions named linear are both
big-o of n. It doesn't matter that one of them has a smaller constant than the other. They both grow linearly -- big-o of n.
And our function from the last video is
big-o of n**2. And now we can compare them.
At a high level, our O(1) function is the fastest. We say it has "constant runtime complexity".
Our O(n) functions are slower -- less desirable -- than functions with a constant complexity. These functions have "linear complexity".
But they are both better than our function with quadratic complexity.
For more practice, complete the rehearse exercises associated with this video and review the explanation video that accompanies them. In our next video, we'll take a look at the complexity of some real algorithms.