# 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. Prashanth H N says:

Doing great work…keep it up

2. sujit kumar says:

thts wht all we need…keep goin..thnku

3. Saurabh Sharma says:

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

4. tushar gupta says:

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

5. varun singh says:

Can u suggest some books for competitive coding

6. Sriharsh Amur says:

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

7. Pritam Gope says:

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.

8. Nipuna Gunathillake says:

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

9. Deepak Roy says:

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.

10. Dina Elhanan says:

AMAZING! THANK UU! I FINALLY GET IT!

11. PS says:

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

12. shobhit sinha says:

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.

13. Christian Balderrama says:

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

14. code_report says:

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

15. Nilesh Kumar says:

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

16. Shackless Shan says:

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

17. venu venu says:

this guy deserves more subcribers

18. abhishek kapoor says:

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

19. Baban Parab says:

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?

20. ishan khan says:

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.

21. Vimal Kumar says:

22. Manpreet Krishan says:

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

23. Nikhil Venkata says:

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

24. G. Russell says:

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.

25. Hiral Ramani says:

Well explained…

26. SRIHARSHA SOMAYAJULA says:

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)

27. Abhishek Sharma says:

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

28. Nakul Bharti says:

Pretty good bro

29. Prannoy Munshi says:

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.

30. Steve says:

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

31. santosh choudhary says:

Thank you, that is awesome explanation.

32. Ashish Shah says:

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

33. Vinay Rajput says:

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

34. Khallil D says:

35. Sheshit Karthikeya says:

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

36. Absolute Quintessence says:

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

37. abhinav pandey says:

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

38. VINAY R says:

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

39. Игорь Бережной says:

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

40. Deshmukh Ganesh says:

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

41. a little coding says:

will come back to this video later. haha

42. Urban Punjabi says:

audio sucks …otherwise everything fine

43. Ihtesham Ahmed says:

thank you Gaurav! that was a good explanation

44. Mahi MSD says:

R u studying or working somewhere….?

45. Ujjwal Roy says:

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

46. Denis Rahim says:

great video man 😛

47. abhay patil says:

thanks from PK and AP

48. Shravan Pandey says:

voice is not clear

49. Vivek Kumar Singh says:

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

50. Azhagi Transliteration Apps - அழகி says:

Very very good.

51. Sandeepraj Singh says:

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.

52. anil anil says:

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

53. Jonathan Osei-Owusu says:

Very helpful and clear video–thank you!!

54. Kishan Mehta says:

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

Thanks for information sharing….

56. Ayeman Bin Salauddin says:

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 !

57. p.b uday says:

By far the best explanation of log n

58. Balkrishna Phale says:

59. ARCHISH MORE says:

in which year of btech do we learn this stuff

60. yiğit bul says:

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

61. Eskimoz says:

Belle réalisation !

62. Steven Vachon says:

I still don't get it.

63. Omi Khan says:

I dont understand ur lecture

64. Barış Velioğlu says:

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

65. Vanessa I says:

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

66. MURHAF AL-MSRI says:

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

67. vikingnavy007 says:

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.

68. Peter Punnoose says:

sub samaj aa gya mujhe … lol

a mic?

70. Isan Bothra says:

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

71. anirudh pundir says:

Great Stuff man……

72. DEBNATH KUNDU says:

somebody give this guy a medal…

73. Vaibhav Jain says:

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