Simplifying log(N) in Algorithms

Simplifying log(N) in Algorithms


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!

73 thoughts to “Simplifying log(N) in Algorithms”

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

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

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

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

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

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

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

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

  9. 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?

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

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

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

  13. 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)

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

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

  16. You are superb bro!!
    Loving your thought process and the way you are delivering it.
    Very immersive.

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

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

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

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

  21. 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 NOT well done.

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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *