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.

Which means

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

it's log(n).

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.

Because there

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!.