(upbeat music)
- Let's say in your coding interview,
you're given a problem and you come up with two separate
solutions, or two separate functions.
How do you know which one is a better solution?
How do you know which function
runs faster than the other one?
You should be able to answer a question like this,
because it's very common for the interviewer to ask
something like "how efficient is your solution?"
And time complexity and big-O notation
are really good tools for answering this type of questions.
Now, as an example, let's think about this question.
How long does the following function take to complete?
In the function, we first initialize X to zero
and for each item in the given list, we add that item to X.
After that, we're going to return X.
So this function simply finds a sum of
the items in the given list.
Now, how long does this function take to complete?
It's actually a really hard question to answer,
because it depends on many, many factors,
such as the performance of your computer and whether or not
you're running other programs at the same time.
And also which language you're using, whether it's Python,
Java, or C++. One way to find the time
a given function takes to run is by running experiments.
You can do this by running this function with inputs,
with different sizes and measuring how much time it takes to
complete each time.
But of course, this option is usually not available in a
coding interview setting.
Or alternatively, you can get a rough idea
of how long it takes to do some kind of analysis
without running this function on a computer.
And time complexity and big-O notation
are tools for exactly doing that.
Time complexity and big-O notation
are a pair of powerful tools for understanding
the efficiency of your function without
actually running it on a computer.
Let's first take a look at how time complexity works.
To understand what time complexity is.
Let's take a look at the function we introduced,
which finds the sum of all items in the given list.
And we're going to plot the time it takes to run this
function against N or the number of items in the given list.
So N represents the size of the input.
Suppose that after running some experiments,
it turns out when N is zero or when the list is empty.
This function takes 20 milliseconds
to run in your particular environment.
And let's say every additional for-loop
turns out to take one millisecond.
So when N is equal to one,
or when there is one single item in that list,
this function takes 21 milliseconds.
When N is two, T becomes 22 milliseconds and so on.
And when there are 10 items in a given list,
this function takes 30 milliseconds.
So the time it takes to run,
this function grows linearly or like a straight line.
And so this function is set to have linear time complexity.
Now let's take a look at this function.
This function is very simple.
Whatever the input is,
we initialize X is zero and then we return it.
So it always does the same thing, regardless of the input.
Let's say when N is equal to zero or when the list is empty,
this function turns out to take 20 milliseconds
after doing some experiments.
What happens when N is equal to one?
It still takes 20 milliseconds because
it doesn't do anything with the list.
It's the same thing when N is equal to two, three and so on.
So this function takes the constant amount of time,
regardless of the input.
That's why this new function is said to have
constant time complexity.
Let's take a look at another function.
This function expects a two dimensional array
as the input, and it goes through each item
in the array and sums it up.
Now let's say that this array is always square-shaped,
which means that the number of columns is always equal to
the number of rows.
And, N here is the number of columns,
which is also the number of rows.
So the number of items in the 2D array would be N squared.
Let's say when N is equal to zero,
or when the array is empty,
this function turns out to take 20 milliseconds to run
without any for-loops to run.
When N is equal to one, we need to run one for-loop.
And let's say each additional for-loop
happens to take one millisecond here.
So this would take 21 milliseconds.
When N is equal to two,
we would have four items in a given 2D array,
just like the example shown on the screen.
And we need to run four for-loops in that case.
So this function would take 24 milliseconds to complete.
When N is three, we need to run nine for-loops.
And so it would take 29 milliseconds.
And if you draw a line that connects these points,
the shape of this line is similar to the function and
squared, which is a quadratic function.
And so this function has quadratic time complexity.
Comparing this to linear complexity,
you can see that it grows much, much faster.
Time complexity is a really convenient way
to get a rough idea about efficiency of
a particular function.
However, it's hard to know which time complexity,
a more complicated function might belong to.
For example, what if we combine
two or more functions together and made a new function?
What time complexity would that function have?
It's also a somewhat awkward way to describe the efficiency,
because we'd need to remember to use different words for
different complexities, such as constant, linear quadratic,
and so on.
Big-O notation is a way of indicating how complex our
function is, and how much time
it takes to run your function.
It's also a convenient way to express
the time complexity of a function,
and it comes up a lot in a coding interview.
Let's take a look at the function we saw earlier.
This function ads up all the items
in the given list or array.
The time it takes to run this function grows linearly,
or like a straight line.
And it can be written as T equals AN plus B
where A and B are constants.
The fact that this grows linearly or like a straight line
can be represented by writing AN plus B equals big-O of N.
This can be also read as the time it takes to run this
function T grows in the order of AN.
There's a simple way to find what should
be inside the big-O expression.
You first need to find the fastest growing term in T.
We have two terms in T, AN and B
and obviously AN is the faster growing term here.
Then we ignore the coefficient of this term
or A in this case, and we get N.
We put this in big-O and we get big-O of N.
Now let's take a look at this other function,
which just initializes X to zero,
and returns it without doing anything with a given list.
The time it takes to run this function
can be written as T equals C, where C is a constant.
And C here is of course 20,
since the function takes 20 milliseconds
to run regardless of the input.
How can we express the fact that
this function has constant time complexity with big-O?
We first need to find the fastest growing term in T
which is 20, because it's the only term.
And then we need to ignore the coefficient from this term.
But 20 is the coefficient itself here.
One way to think about this is,
we can rewrite 20 as 20 times one.
So this is big-O of one.
How about this function that adds up
all the elements in a two-dimensional array?
And here is the number of rows as well as
the number of columns. And so the number of items
in this array is, N squared.
The time it takes to run this function can be
written as T equals AN squared plus C,
where A and C are constants.
And this is a quadratic function.
So this function has quadratic time complexity.
Using big-O notation, how can we express
the fact that it has quadratic time complexity?
We first need to find the fastest
growing term in T, which is a N squared.
When we remove the coefficient A from this term,
we get N squared. Put in N squared in big-O,
we get T equals big-O N squared.
Let's go back to the function
we saw earlier once again.
This function ads up the items in a
one-dimensional way or a list. T is written
as AN plus B here, but to be precise, B is 20,
because when N is equal to zero T is 20.
And A is one, because our assumption here
was that each additional for-loop takes
exactly one extra millisecond.
Now let's say you're running this function on a computer
that's twice as slow as a computer we were using originally.
Then this function would take twice as much time.
Let's call this new time T2.
Everything would be multiplied by two,
so T2 is equal to two times N plus 20,
which is equal to two times big-O of N.
This is equal to two N plus 40.
Now let's think about how we can rewrite
this expression using big-O notation.
The largest term in T2 is two N.
So we just need to take out the coefficient,
which is two, and we get N.
So T2 is equal to big-O of N as well.
So two times big-O of N, is actually equal to big-O of N.
In this way, big-O notation and time complexity
have a really nice property that they don't
depend on a particular environment
that you're running your program on. Whether your computer
is 10 times slower or 10 times faster,
this function would still have linear time complexity,
and it can be still written as big-O of N.
Let's take a look at another example.
This was a function that doesn't do anything
with the given input.
It always takes 20 milliseconds to run,
or it has constant time of complexity, big-O of one.
Let's say you just switched to using a new environment,
that's five times as slow as the original environment that
you were using.
Then this function would take 100 milliseconds
instead of 20 milliseconds to complete.
Let's call this new time T2.
This is still a constant, so it can
be written as big-O of one.
So five times big-O of one, is equal to big-O of one.
Changing an environment doesn't change
the big-O here either.
In summary, we saw that two times big-O of N,
is still equal to big-O of N, and five times big-O
of one is still equal to big-O of one as well.
In general, if you multiply a big-O expression
with a constant, the big-O expression stays the same.
Or a constant times big-O of X is still equal to big-O of X,
whatever X might be.
whether it's N, one or N squared.
Another way to put it, is that the time complexity
and the big-O expression do not depend
on how fast or slow your particular environment is.
This just express how fast the runtime,
or the time it takes to run your function
grows as the size of the input grows.
(upbeat music)