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!

Doing great work…keep it up

thts wht all we need…keep goin..thnku

It looks like Meta-binary search. Is that actually the case?

When we are searching for a number in an array , how come we are actually defining a log(n) digit number?

Can u suggest some books for competitive coding

Can You make a video on how to Win IOI(International Olympiad of Informatics)? Please, I have 10 More Months, How do I prepare?

How to find third largest number in an array of size 10^9. Assume array is filled with random numbers.

need to solve this in efficient way so that it will take less time.

please help!!!

Great set of videos. Looking forward to seeing even more!

I just want to know in O(log(n)) how much iterations are require for 1-2 secs.And tell me the process also how you calculated it.

AMAZING! THANK UU! I FINALLY GET IT!

Here is alternate explanation, probably easier for people with mathematical mind / background –

log(X,Y) or log of X to the base Y or (ceil of it) is number of times X should be divided by Y till it reduces to 1 or less than 1 (which ever happens earlier), that is why log(X,Y) is number of places(or digits) in base-Y number system to represent X. Binary search (or Y-ary search) takes log(N,2) (or log(N,Y)) because it divides problem of size N( into 2 or Y pieces) repeatedly until problem is trivial (1 element array) – and number of division operations needed to reduce problem of size N to size 1 is log(N,Y). Sorting – why n x log(n)….assume or imagine that you have sorted imaginary clone of unsorted array. What you're really doing is performing binary search for each item in unsorted array in its sorted imaginary clone but binary search is to find "sorted index" for an item in unsorted array. You have n items in unsorted array, you're doing binary search for each of n items – so your complexity can not be better than n x log(n).

P.S. I found explanation above little hard to understand

thnx for making videos like this, yes its hard for beginner but you don't see them everywhere on internet. Make more videos like these.

Please make Data Structure playlist!!!!!!!!!! <3

Hi Gaurav! I just started a competitive programming YouTube channel! I would love it if you gave me a shout out! https://www.youtube.com/channel/UC1kBxkk2bcG78YBX7LMl9pQ

Sir , could you please make video on SOS DP technique . Questions on this technique are asked frequently these days. Thanks in advance 🙂

Content Is Good . Sound Is Clear But keeps on bouncing from high note to Low …Fix that if possible

this guy deserves more subcribers

sir, please please make a video on dynamic programming with convex hull optimization. i tried to under stand this technique but never could understand it completely. here is the description from https://wcipeg.com/wiki/Convex_hull_trick

bro i just watch your codedojo interview that was very nice. i am 3rd year mumbai university .i am interested in machine learning are job available for beginners in india for AI and machine learning ?and for interview what they focus on more technology knowledge (like tranding programming languages like python ) or they focus on algorithm?

How much this competitive programming stuff comes to use when you are working in an IT service industry where you are don't face some interesting problems and you have to collect some pieces from here and there and compile them together to make a product according to clients requirements.

nice video, really helpful (y)

Please consider using a microphone (the one you attatch to the shirt or whatever kind). Thank you (:

Audio quality makes a major role when it comes to video, To select your video instead of 100's of others in YouTube you should make your video more clear..

So better buy a small mic and attach it to your shirt

I love this explanation. It made things more clear with how logarithms are actually applied to N. Log base 10 of N is slightly less than the ceiling of log base 10 of N. and the answer is the minimum number of tries to uniquely identify a number within that range. Wow, thank you.

Well explained…

We take an array even in linear search as well but why is its worst case is o(n), and why binary search takes o(logn)

I just chanced upon your channel and got lucky ! Very good.

Pretty good bro

Everything is good, but that explanation as how did binary search came down to logn (that is 5 in this case) is somewhat hard for first timer. Maybe you can explain for 29713 how it's 5 times by actually giving a quick logic?

Just a thought. No sweat.

it's great! Keep going with what your passion lead you too 🙂

Thank you, that is awesome explanation.

I found it difficult to understand from part 2.10 to 3.7. Can you please explain?

dude, you are really good,

but your explanation on board is quite messy, which confuses viewer, possibly you need to redo this with organised on board explanation,

and I am still not clear, why log(n) + log(n) …. log(1) = log(n!), how log(n!) == n*log(n) – n,

Thanks for your efforts, let me know if you have time to share more knowledge, I am subscribing to you channel

the microphone please

You are superb bro!!

Loving your thought process and the way you are delivering it.

Very immersive.

Awesome video.. I am glad I found your channel. Please do some videos on preparation for ACM – icpc.

Could you share a problem list in online judges which can be followed to learn competitive programming

Very good video man. So far the best explanation of logarithm i have come across. Thanks and keep posting.

nice one have to watch this video like 10 times more!

please add more topics for beginners, as no channels are available for Competitive Programming, except yours.

will come back to this video later. haha

audio sucks …otherwise everything fine

thank you Gaurav! that was a good explanation

R u studying or working somewhere….?

Man…this was an amazing experience. You just proved my whole understanding of time complexity WRONG…

great video man 😛

thanks from PK and AP

voice is not clear

Can be good for experts but definitely not for beginners, after the initial few mins of the video it started bouncing, make another for beginners

Very very good.

Sorry, have watched this over and over but Beginning 5:10 to 6:49 where you suggest that "searching will take log(n) operations at the least" is not clear. The example you provide after that with hand gestures..You kind of just zoomed past. That was the meat of the video and the job there is

NOTwell done.Hey i am anil from IIT Delhi & i have some problem in learning sml language give me some instructions please…….

Very helpful and clear video–thank you!!

Hey, Gaurav Please explain Manacher's algorithm to find a longest palindromic substring in a string.

Thanks for information sharing….

I think this channel can be the next 'thenewboston' , I mean millions of subs. cz contents are amazing.

btw im 15, and love from Bangladesh !

By far the best explanation of log n

Your explanation is complicated.

in which year of btech do we learn this stuff

I've seen many videos and never ever seen this explained as well ! not even close !

Belle réalisation !

I still don't get it.

I dont understand ur lecture

One more time you did a really good explanation on a tough subject.

Your videos are great. I understand your logic very well. It's how I think too. Thanks for this!

in 8:25 when we mapping that number in the new array how we can actually know the right place for that number.

In computer science it is understood that the base for log(N) is 2 (not 10). This says you are "halving". How many times you must split size N in half. For a balanced binary tree, there will be 1+ log(N) levels.

sub samaj aa gya mujhe … lol

a mic?

Good but bit messy.. I guess that the Log(N) value is the total number interation needed in worst case scenario for binary search

Great Stuff man……

somebody give this guy a medal…

Can`t believe, how easily you explained it. Changing perspective to look into Binary Search was eye opener to me. Great bro