Hi everyone, this is gkcs! We are taking about
why log appears many times in complexity analysis. So if you're just starting off and maybe you
came up with binary search. You see binary search. And you see the order
complexity for this algorithm is order logN. For the range 0 to N. So this is actually
a very interesting result and we will get to this. But logN is something that we should
look at. The next thing is sorting algorithms. For example, merge sort. Time complexity for
this is O(n*log(n)). And again, interestingly, a wild log(n) appears. Why is this? Well log(n) has an interesting
property. In fact, some interesting things have log(n) as their property. So if I write
down a number: let us say 29173. Right now what I'm doing is I'm keeping some
information in this number implicit. When I'm coming to a human being, 29173 something. But let's make that explicit. What this is,
is 2*10^4 + 9^10^3 + 1*10^2 + 7*10^1 + 3*10^0. So the implicit information is actually the
base. The base that we are using. We usually use decimal as our base because it's so common.
But computers use binary. You can use ternary,
you can use whatever you like. But the base is important when you're representing information,
because you'll notice that the the number of digits you need in this number is directly
proportional to the to the maximum exponent that we need of 10. This number is smaller than 10^5. If we call
this X, then 10^5 is greater than X. So what we can say is that the number of digits you
need to represent a number in decimal is going to be the maximum exponent slightly greater
than the number itself. Simply put, easy! That's it. So if I take
log(X) get to the base 10 this is going to be less than five. And so slightly greater
than X which is log(10^5) to the base 10 is equal to five.
And what I can then do is I can just say take
the ceiling of log(X) to the base 10 and what will happen with this thing is: this number,
is the minimum number of digits you need to uniquely identify the number X in the range
zero to X. I want to make that very very clear. To Uniquely
identify a number between zero to, let's say this 10^5 is n.
So from 0 to n – 1, if I need to uniquely
identify a number X, I need log(n) digits. In fact, from 0 to X also it's less than log(n)
digits maybe. But from range 0 to n – 1, number of digits
you need to uniquely identify a number X is log(n). Right, that part is clear. Because
we just proved it taking the largest exponent. Of course, log(n) to the base 10 is what we
talked about earlier in human language. But for a computer everything is binary so log(n)
to the base 2. This number will be represented in binary in log(n) to the base 2 bits. So
this is the reason why log(n) appears. log(n) bits are required to represent a number. But this also tells us something else. To
uniquely identify a number in a given range 0 to n – 1, you need log(n) bits.
that if I have an array and I say that I need to search for a value. Some value B, and the indexes are from 0 to
n – 1. Essentially what I'm saying is for this index, for this value actually, give
me an index I want this value to be mapped to. An index which has some some specific property,
basically I want to find where this value exists. So when I say that any algorithm will
actually take log(n) operations the reason for that is you have a range from 0 to n – 1
as your indexes. You're searching for one unique index. To
identify that you need at least log(N) operations. Very similar to how you can you can define
a number in log(n) bits. You need at least log(n) bits to define the
number. You need at least log bits to search for that particular number in this array. Ok? So take your time to know understand why
Because it's not like you already know the number you're actually finding it
and every time you're finding it- You are basically taking one digit and choosing
a value for that digit. So if this was decimal then you would have 10 values when you choose
one so in this case we would choose 3. Down that path we could then choose the next
choice which is 7 and in the expanse of 10 raised to power 6 values we will be choosing
one. So of course visually you can think of it that way but simply put: you need log(n)
operations for this search. You are choosing one by one by one. Just like you choose digits in this representation.
So it takes you log(n) time. Okay, cool! If you can wrap your head around that, then
we have something even tougher! Not really. We will be using this result of
log(n) of a search. The best search in the world, it could be by binary search, ternary
search: whatever you like.
Penta search. It's going to take you log(n) and based on
of course whether you are using binary search or ternary search, this base is going to change. But the order won't change and you can think
of that by yourself. There is a video for order complexity that I made yesterday. It's in the in the description below and also
I will keep a card up there. Have a look at that if you if you are not sure with order
complexity. Okay now! Sorting algorithms, like merge sort
or quick sort. All of them have n*log(n) worst case time complexity. Technically quicksort
has even more. n*log(n) is the time complexity that we usually meet. Why is that? What is sorting actually? Sorting is like
taking one array which is input. And indexes from 0 to n – 1 is this array.
n elements. And the output is from 0 to n – 1. You need to map these elements to this
array. Each element needs to be mapped to its corresponding
index in the sorted array. So how do we do this? Simply put, if you take any element and try
to map its corresponding index is this array you cannot perform better than the search
algorithm we already had. The optimal search algorithm. Which is going to take you log(n) time. Because
there n spots, the range is from 0 to n – 1. You need to choose one spot. To find that
correct spot it's going to take you at least log(n) time. The next element, let's pick this element,
has n – 1 spots to pick from. It will take at least log(n – 1) time plus log(n – 2) time
for the third element.
Plus so on and so forth upto log(1) which
is 0. Okay, but the important thing here is that there's a property: log(a) + log(b) equals
log(a*b). Even if you don't know this, what I can tell you is that, it exists. This whole term then turns out to be log(n
* n – 1 * n – 2 ….). So that is log(n!). Right, very interesting! Now we don't know how to break this down,
there are some approximations, but let us simplify even further.
N*log(n) is what we are looking for as the
worst case. So n – 1 is definitely less. n – 2 is the definitely less than n. I'm going to get rid of these guys. The -1,
-2 factors and I'm going to make them all n. How many times do I need to search for
an index? How many terms exist this? n. So this is going
to be n * log(n). That's it! We have proven that there cannot be a sorting
algorithm better than n*log(n).
Of course, you must be wondering what is this value.
It's definitely less than this. If you do some sort of approximation what
you'll end up with is: this value approximates to n*log(n) – n. But when you take the order
complexity this value is less, I mean this degree is less than this so you get rid of
minus n and you're left with O(n*log(n)). It might be slightly hard, if you're just
starting out with algorithms. But for an intuitive understanding of sorting algorithms and binary
search, you can always come back and you can have a look at why the log(n) factor keeps
in appearing computer science. The most important thing? To define, uniquely
define, a number in a range from 0 to n – 1 you need log(n) bits.
Log(n) digits, log(n) bits, whatever you'd
like to call it. Then when you're searching for a number between 0 to n definitely you
need log(n) operations. Because you are defining it as you move ahead.
As you search for it we are actually defining the number. And because that's the amount
taken in a binary search thing from 0 to n – 1: sorting algorithms are nothing but choosing
the right index for each element in the sorted array. It's a permutation of these elements to this
point. So the mapping for every element is going to take you at most log(n). It's going
to take you slightly less actually, but at most log(n).
So for n elements log(n) operations = n*log(n).
Of course, if you are very picky, then you can you can approximate this to still be O(n*log(n)). If you have any doubts or suggestions, leave
them in the comments below. This is likely heavy for a beginner so you might want to
revisit this or if you have any solutions to make it even easier please leave them in
the comments below.
I'll see you next time!.