Why the FASTEST Sorting Algorithm can(t) be O(N)!

[@mohitthorat8580]

You said to express a number we require atleast Log(n) operation. But we don't include this in the Time complexity analysis of bubbe sort, still it's completely is O(N square). Why? Shouldn't it be more than N square?

[@gkcs]

I think this part of the video is the most misunderstood bit, and I take responsibility for not communicating my thoughts accurately: A number takes logN bits to represent. When we choose a position for it to be placed, the index will take logN bits to represent. Each bit requires a decision to be made -> 0 or 1. Hence we make logN decisions for deciding a single position amongst N positions. This is how I came to the series logN + logN - 1 + logN - 2 + ... + 1 Bubble sort goes through the numbers ahead of it. Each comparison is assumed to be an O(1) operation. This makes sense because the computer hardware can compare 32/64 bits in a single operation, and we rarely sort numbers larger than that. If you sort an array of arbitrarily large numbers, the complexity of bubble sort will be O(N^2* log(N)). The same as bubble sorting strings of size L: O(N^2 * L). If L is small enough or constant, the complexity reduces to O(N^2), since the factor of L is ignored.

[@mohitthorat8580]

@@gkcs Makes sense. Thanks!

[@noasmr46]

Gaurav Sen why does a number take LogN bits to represent? If bits are only 0 and 1 won’t a number like 255 need 8 bits (11111111)? But log(255) base ten is 2 so only 2 bits to represent?

[@khannom1693]

@@noasmr46 I think he meant log base 2 of N

[@gkcs]

@@noasmr46 A bit is a digit in the binary world. A decimal digit is a digit in the decimal world. You are mixing the two. Binary? log(N) to the base 2. Decimal? log(N) to the base 10. Check out: kzbin.info/www/bejne/jpackqRnjLGjoLc

[@SongSoundGood]

There is a sorting algorithm working in O(n) called eliminationsort. You eliminate every element that is out of order. By the end, you have a sorted list.

[@gkcs]

The comments today on this video are awesome :D

[@XeartyBG]

This comment is great :D

[@nguyenduckien1477]

i optimize your alogrithm by delete the whole list

[@pranavchaudhary7538]

Also knowns as HitlerSort

[@anshumanchaursiya3704]

@@gkcs so is it true that elimination sort takes o(N) time?

[@TonKcedua]

Actually, the Faith Sort's time complexity is O(1) - you just take the input array, put all your faith in it being already sorted, and return it. Worst case scenario whatever god you believe in takes care of the rest.

[@dhruv0x0x0]

bruh....

[@lakshmanvengadesan9096]

😂😂😂😂😂

[@niveyoga3242]

😂😂😂😂

[@ShyGuy_16]

🤣🤣

[@BillNice]

😂😂

[@souravkumarcode]

This is what clickbait looks like for computer science students.

[@g_r_s4532]

souravk229 lmao 😂

[@yogeshratudi2061]

😂😂😂😂

[@안해찬-i9i]

It worked 😂

[@fuseskyplays3111]

He got me 😪

[@princeakhil208]

O(n) hahahaha

[@ubermensch9678]

Ever heard of Schrodinger's + Heisenberg's sort? 🤩 The array is already sorted as long as....... You don't look the array 😂

[@raunvk]

Brilliant XD

[@ron-davin]

lul

[@ryzen980]

smart!

[@pi_rand4266]

Best comment

[@vineeth505]

It is both sorted and unsorted at the same time until you look at it to be precise😂 Cool one though!

[@MeFreeBee]

The trick to faster sorting is to always buy your data pre-sorted!

[@gkcs]

Hahaha!

[@Rahul-Nalawade]

This is where he could have talked about best case for Insertion Sort.

[@khhnator]

is a joke, but that's pretty much what high performance programs try to do: push all extraneous calculations to before you actually needs to run the program

[@maciejmalewicz9123]

Assumption sort. Assume its sorted, return.

[@kongchan437]

@@maciejmalewicz9123 ----- I go one better - I do not even have to assume it is sorted. I will just declare it sorted already, in the order of whatever the list is already showing.... hey, why bother to sort at all … you get whatever you see...by the time we spent discussing all these optimal sorting techniques, the brute force program code would have run the job many times over, right ? :-)

[@tjoloi]

"O(n) is not possible" Do you want to learn about our lord and savior Sleep Sort?

[@gkcs]

Hahahaha 😝

[@khhnator]

i stand by the word of Gravity sort

[@satibel]

in all seriousness, O(n) and even O(log(n)) time are possible with parallel sorting networks. though they can only sort a fixed n, if you need a really fast sort for n

[@dale116dot7]

Radix sort I think is O(n). It works really well if you drop your deck of FORTRAN cards and you need to get them back in order.

[@tusharsingh2439]

pregnant woman: (hits blunt) it wont affect my child. the child: let's use bubble sort.

[@JeffHykin]

Actually, at the extremely low level of an L1 CPU cache (very small lists, very small data), bubble sort takes the least amount of real time. It's faster (in memory) to access and compare cached nearby elements than it is to go get elements from RAM and put them in the cache.

[@dr_davinci]

Nah, he be using bogosort.

[@tusharsingh2439]

@@dr_davinci delete sort, better

[@purple.requiem]

@@tusharsingh2439 no its worst sort

[@Draxper]

@@JeffHykin no, for small lists, insertion sort works best. As a matter of fact quicksort is also supposed to use insertion sort once partitions are small enough

[@SlimThrull]

Random Sort is able to do it in O(n). It just doesn't happen very often. ;) C'mon, you know you deserved this comment for that title. :P

[@gkcs]

Hahaha!

[@ivosu4936]

I thought it is in O(1)

[@gkcs]

@@ivosu4936 You need to verify the guess too 😛

[@ivosu4936]

@@gkcs or you can just roll with it, cause in one of manny parallel universes it is sorted

[@dhruvilpatel856]

You might be knowing this, but time complexity has to taken considering all cases instead of just best cases

[@bruhe3178]

Good content but bad clickbait ): The fastest sorting algorithm should have been O(1): By pointing to an empty list. An empty list is always sorted.

[@gkcs]

Hahaha!

[@ShubhamKumar-sq2pg]

or a list with only one element ;)

[@ryzen980]

lol!

[@rajtiwari2308]

We are talking about the worst case here, Don't even write a program it will be O(0) 😂

[@Yash-_-777]

youtube guy explaining fastest sort algo: me simply using .sort() method in python : KODER!!!

[@ItachiUchiha-ub2iu]

That .sort() in Python is using Timsort algo developed by Peter Tim, having worst and best case as n*log(n).

[@Yash-_-777]

@@ItachiUchiha-ub2iu yes that's similar to merge sort I Guess

[@nehalgupta79]

O(1) for sure m8

[@janhavisavla9654]

Thanks to your videos. You're one of the reasons I'm placed today, that too within 15 days since the inception of placement season in my college. I used to suck at coding, now I can safely say that I'm amongst the top 20 coders of my class(PS: my college(VJTI,Mumbai) has very good coders ) . I am placed in Accolite (which recruits only 60 engineers all over India , I was amongst the 6 people they chose out of 300 students in a pool campus process,went through 1 written coding round , 3 gruesome tech rounds and one HR round ). I went till the last round of Morgan Stanley (top 5,but they chose only 2 sadly) and your system design videos helped me a lot through the process. Now I've started competitive programming and I'm enjoying it a lot. From a person who didn't get a single internship last year, to being amongst the first students to be placed this year. You've inspired me. Thank you! Keep up the good work! :)

[@gkcs]

I am super impressed Janhavi! Congrats! 😍

[@nabanjand]

Well, any comparison sort where one compares the elements to each other cannot be done in less than O(nlogn) time! Non-comparison sort like Bucket Sort can be in O(n) (The special conditions required for bucket sort are: 1) The values to be sorted are evenly distributed in some range min to max. 2) It is possible to divide the range into N equal parts, each of size k. 3) Given a value, it is possible to tell which part of the range it is in.)

[@LucidProgramming]

Hi Guarav. I really like your content, and this video is no exception. I understand the marketing realities present on KZbin force one to make "clickable" titles. I really don't want to see smart channels like the one you run devolve into the Buzzfeed of KZbin. Granted, this is a far cry from the typical clickbait, but I just don't find those tactics to be genuine. I wouldn't take the time to comment on other channels employing these same tactics, I just feel like the quality of content you usually produce is above the clickbait tactics. Hope you take this as constructive criticism, and not as a personal attack.

[@gkcs]

I will, thanks for the feedback! 😁

[@nirmitjoshi5741]

He has mentioned that in comment section. Don't watch it if you don't find it useful. Gaurav keep it up I loved this video. Why do we learn this ? 😎😎😂😂😂

[@vedprakash-bw2ms]

This was a click-bait.

[@manasgunda1421]

Yeah click-bait, but good video

[@arwahsapi]

Dozens of years of my life as a programmer, I mostly use Sort() method in almost C# collections. I never care how it works. You have explained the subject very well mate. Thanks

[@JAYPRAKASH-uy8rg]

My senior who works at a MNC suggested me your channel for system design videos, and trust me if I am saying that this channel has great great content for budding fresher's. A big fan of yours 🙌🏻

[@nomads27]

Nicely explained, but that God part is little confusing, instead of that it would be better to say, 1) Comparisons will be at-most height of your decision tree 2) no of leaf nodes of this tree would be n! i.e. no. of permutation possible 3) and h >= log(no. of leaf node)

[@BikashKumar-pz8hc]

I totally and absolutely love the creative treatment. This video always brings up a smile. What's more the explanation is clear to an non-computer science student like me. Great work Gaurav Sen.

[@farruhhabibullaev5316]

More correctly, I would say "comparision based sorting algorithms best run time is nlog(n)" but integer based sorting algorithms such as counting, radix & bucket sorts are run in order of N asympoticially. But not quite O(n), the best one is O(n*sqrt(loglogn)) but it's hot research area at the moment, we can't claim it's impossible without any proof.

[@Matyanson]

Where can I find any info on this? What is the name of the concept algorithm?

[@sagnikb7]

I came here for System Designs ! But omg now I have started learning logarithms, such a wonderful video ... especially where u prove fast sort cannot exist!

[@gkcs]

Thank you!

[@keshavlakhotia1432]

Gaurav Sen found a friend good in video editing XD

[@gkcs]

One of the Gaurav Sen's in the video helped me :P

[@keshavlakhotia1432]

😆

[@subho3651]

@@gkcs very soon we will ask you to teach us video editing.

[@blasttrash]

No he learnt shadow clone jutsu from naruto. :P

[@apolishchuk1880]

counting sort is O(N) if values range is bounded

[@victorcaldentey6295]

Best intro ever in an Algorithms video!

[@gkcs]

😎

[@rookandpawn]

The comments here are not really thoughtful. This video was an excellent presentation on the subject and a great intutive dive deriving naturalistically the big O from permutation trees. Thank you Gaurav for this. Super awesome video.

[@gkcs]

Thank you!

[@shivukotihal3366]

This is high level punch for cs students. I will prove you wrong just because of this video. Jai mahishmathi

[@gkcs]

Hahaha!

[@davidjames1684]

One "simple" enhancement to a sorting algorithm that only grabs the largest (or smallest) number each pass is to grab both. For example. suppose we had ten scrambled numbers to sort between 1 and 10 (such as 7,4,6,1,8,10,5,3,9,2). The "hi-lo" sort algorithm would make a pass thru all 10 numbers and would record the position of the lowest and highest numbers (position 4 = 1, position 6 = 10). It would then put the 7 in temp memory (since we need to move the 1 there) and would also store the 2 in temporary memory (since we need to move the 10 there). The new array (after the first pass) would be 1,4,6,7,8,2,5,3,9,10. Now we can sort the subarray (4,6,7,8,2,5,3,9) since we know the 1 and 10 are already in the proper positions. I am calling this the hi-lo sort. It is a good start to try to improve on such as maybe try picking off the 2 highest and the 2 lowest numbers each pass. I realize this is somewhat similar to the cocktail shaker sort except that the direction can always be low to high index in the array of numbers, thus perhaps making it slightly easier to implement.

[@kushalchordiya7229]

This was a great video On a completely unrelated side note, you look like kanan gill and biswa Kalyan rath had a child.

[@gkcs]

Hahahaha

[@nithishpai]

You forgot to maintain an important point. The lower bound is Ω(nlogn) for comparison sorts. It can be less than that for other classes of sorting algorithms.

[@GRBtutorials]

Next up, do the slowest sorting algorithm ever. Bogosort is slow, but there are slower ones! I've personally designed what I believe is the slowest optimal (without doing unnecessary steps) sorting algorithm ever, QuantumSort: 1. Check if data is sorted and if it is goto 3. 2. Goto 1. 3. Return data and exit. How does it work? Simple: over time, random quantum events (such as cosmic rays) will modify the data in RAM until it's sorted.

[@gkcs]

Interesting. Won't the heat death of the universe happen first?

[@GRBtutorials]

Gaurav Sen Most likely yes

[@ankurxshukla]

This guy makes most precise videos..

[@vedant6633]

Radix sort can practically do it in O(n)

[@nikolatasev4948]

He just proved mathematically that Radix sort does not exist! At 8:04. Who are you going to believe, him or your lying eyes?

[@robertlittlejohn8666]

The video uses an incorrect version of Stirling's approximation for N! It is log N! = (N+1/2) log N - N + log sqrt 2*pi + O(1/N), and these are natural logs. The most important term omitted by the video is -N.

[@gkcs]

In the order complexity analysis, the -N will be removed. Hence I ignored it.

[@gopishivakrishna9707]

haha.. laughed at the start looking at so many YOU.. Simple and neat explanation... I've been watching your videos lately and guess what ? You have a Subscriber ;)

[@ImperatorZed]

Pigeonhole sort is O(n). We don't use it because it only works on fixed value possibilities

[@HCTripleC]

Your proof is valid however it only applies to comparison-based sorting, as those algorithms are reliant on relativity between one another. Since non-comparison based sorting are all based on the foundation that you can sort a data set with no knowledge of any other piece of data except for the one which you are ordering. It is this fact that permits non-comparison based sorting to have a better worst-case time than O(n log n). The limit for a non-comparison based sort would be O(n) since you would have to access each data member at *LEAST* once during the sort. Proof: Let X(n) be an unordered data set of n items, and let Y(n) represent the ordered data set of X(n) Let H(v) be an ideal hash function which maps a member of X(n), v, to its corresponding index in Y(n) If O(H(v)) = O(1), then the number of steps needed to perform to create Y(n) would be: S = O(H(X(1))) + O(H(X(2))) + . . . + O(H(X(n))) = O(1)_1 + O(1)_2 + . . . + O(1)_n = n * O(1) = O(n)

[@benswanson4807]

yasss

[@gkcs]

That's correct, thank you for pointing it out :)

[@NitishRaj]

Thanks Homer Calcalavecchia sir.

[@khushitshah979]

What about collisons in hash function.. that can end up in O(n) instead of O(1) so we need completely collision proof hash function👍👍👍. To achieve these and i don't think there exit one(not sure)

[@neensta5404]

@@khushitshah979 he already stated .." 'Ideal' hash function"

[@SameerKhan-qy7ot]

Me: Trying to print output correctly. GS: Today we'll sort in O(n). :D

[@abhishek-kapoor]

Correct me if i am wrong but asymptotic notation are for machine-independent algorithm analysis but in this video, we are talking about machine-specific analysis which should not be present by the asymptotic notation. 🙃🙃

[@arielfuxman8868]

I did not understand the part at which you started saying "you can represent a number with log n +1 What does it have to do with the permutation?

[@dhruvreshamwala511]

Tricked me into understanding something more fundamentally. Not even mad. Great explanation !

[@gkcs]

Thanks!

[@AshirwadPradhan007]

I liked the old saas-bahu "No no no" part.... btw Great work buddy!

[@gkcs]

Hehehhuhuhuhahahhaha! Thanks!

[@poosaipandiv4947]

Broo first time I see your video Really enjoyed and well understand the concept. I think this is the first video which is watched without skipping.

[@gkcs]

Thank you!

[@pratikbhagwat95]

Ssly yooo... What the heck.. Had lot of expectations from fast sort in the beginning.. Anyway that was really an amazing way to prove that O(n) is nt possible while sorting.

[@arnabsom3251]

Its possible just get a quantum computer you can do it in O(root(n)) time

[@dale116dot7]

I think radix sort is O(n), though that is the running time in a mechanical sorting machine if you discount the gathering of the cards and resetting the machine to run the next digit. Though if you have 100,000 cards sequentially numbered then put out of order, I think there should be 500,000 comparisons and five gatherings.

[@jessyvlogs29]

O(n log n) is only the best fastest sort and I like it as it has a best logic when compare to all other sortings!!!

[@aranjan]

Ohh .... That was really cool 😍 Can you discuss the multiprocessor part to reduce the complexity to O(logN) again ?

[@gkcs]

I'll try in one of the future videos 😋

[@shubhygups]

​@@gkcs if we use N number of processors likewise you said logn number processors to achieve O(N) can't we achieve O(logn) like this? why we need infinite processors than? or similarly nlogn processors to achieve O(1) time complexity to sort array (which is obviously impractical) than why using infinite processors we still achieved O(logn) time. Thanks

[@DanielNyong]

@@shubhygups That's not practical lol unless you have 4 items to sort. Then bogo sort isn't even that bad.

[@alkatiwari6650]

I subscribed it immediately. I am glad that KZbin recommended this. I have seen your video with Anshika Gupta where you were talking that " Agar 8 semester me nahi padha to kya padha". You are too sarcastic. Really liked the way you are teaching. 🙏 Thankyou Gaurav Sir

[@1Maklak]

The fastest pairwise comparison algorithm is O(N*log(N)) and the proof is similar to what you've shown. Basically, a comparison can be enough information to reject about half of remaining possible permutations of numbers. Radix sort (using counting and indexes, not buckets) is the fastest in practice for tens of thousands or more elements and leaves other sorting algorithms in the dust. It IS almost linear in practice, since an array of 32 bit numbers requires just 4 passes, while 64 bit numbers require 8 passes. It is also pretty cache-friendly. Mathematically, n! can be less than or equal to a^b for some a,b

[@shrshk7]

Though it's a clickbait he proved that there's a mathematical limit to how fast we can sort with some help from wikipedia article, I'd say he's smart.

[@nitanshu.v]

Thanks!! I really enjoyed the way you explained the concept.

[@ky5069]

Nice video Gaurav, but I did not understand the transition from the usage of log10 for digit counting to log2 usage when unravelling the factorial. Would the digit count example be applicable for base 2 numbers? Or is the O(n log2 n) the minimum time complexity because you have to do 2 choices for each item (either stay put or move in relation with its compared item)? Thanks!

[@gkcs]

The base doesn't matter in order complexity analysis. log10 n = (log2 n)/(log2 10). 1 / (log2 10) becomes a constant factor.

[@nitishkumar-py9ru]

Nice proof. Never thought in this direction. You explain like biswa Kalyan rath , so I it was more fun.

[@gkcs]

Hahaha, I get that a lot 😛

[@codexhammered007]

Woaah. You got me with the title. I guess python's "list.sort()" or quite famously known as "timsort" is faster than any other sorting module present in any language. Is it so?

[@gkcs]

I am taking a video on Timsort next 😋

[@NarendraPathai]

Java has opted for timsort as well

[@KnakuanaRka]

I don’t know about log N processors, but I do know a way to do O(N) using N processors, called odd-even sort. Basically, implemented in a non-parallel way, you would sort 100 elements like this: First do one scan through the array, comparing the first element to the second, the third to the fourth, 5 to 6, etc; if those two elements are out of order, switch them. Then scan again, but this time compare 2 to 3, 4 to 5, 6 to 7, etc, as well as 1 to 100; swap them if out of order as before. Repeat the scan over the array, alternating between these two pairings of elements as detailed, until you’ve done 100 scans (IIRC, may be 50). Then your array is sorted. Now, this may sound like a strictly worse variation of bubble sort, but the trick here is that each scan consists of 50 compare-and-swap animation between 2 elements, *which are completely independent of each other.* This makes it ideal for parallelization; if you can spin up 50 processors that can each do a compare-and-swap, then you can do the 50 compares in each scan simultaneously, doing each scan in O(1) time, and the whole thing in 100 steps, or O(n).

[@gkcs]

It is a good idea, but what you are doing is similar to a merge sort. The 50/100 passes are dependent on the number of elements you have. It's proportional to log(N). Since N is usually smaller than a billion, less than a 100 swaps suffice :)

[@KnakuanaRka]

Gaurav Sen That doesn’t sound like what I’m talking about (it’s listed as odd-even sort on Wikipedia; basically bubble sort, but a bunch of swaps can be done at the same time). Are you talking about Batcher odd-even mergesort?

[@htxdy]

If you define a constant value for the log(n) variable it will be n log C, no matter how big the C is, the time complexity will always be O(n) h3h3h3

[@htxdy]

Thats basically how counting sort and radix sort works also

[@craigslist1323]

There is a constant time sort I have invented. The only constraint is the numbers itself should be small. Say any number should be less than billion. 1. Take an array of size billion. 2. Insert the respective number into array index of the number 3. Iterate through the array. Voila, you just iterate through the array and you will get the result (yeah you need to do it a billion times, but atleast that's a constant)

[@brucea9871]

You didn't invent it. That sort was thought of long ago but it's impractical because to sort large collections it requires a lot of memory. Moreover as you say the numbers must be small.

[@WittyGeek]

Saw this JIT!! Nice video explaining why O(n) sorting doesn't exists. P.S: The introduction was next level swag!! Keep such things more as it makes it more interesting.

[@gkcs]

Yey!

[@kulwantkaur7794]

Cyclic sort can sort in O(n) when numbers are in range of 1 to n but it's not a comparison based algorithm. A comparison based algorithm can't be faster than O(nlogn).

[@gamingbutnotreally6077]

I can make an Unsorting algorithm in O(1) 😜 Great video Gaurav!

[@jeromeyklein8838]

Here we are making an assumption that we can only use a comparison based sorting algorithm. If we use a data structure to actually store the elements then we can benefit from the structure of the data and do better than nlogn.

[@arglebargle17]

This past weekend, just to keep myself sharp, I benchmarked a bubble sort, a quick sort and a radix sort on varying numbers of random integers. The bubble sort did as badly as expected. But on 1 million elements, the radix sort was 5 times faster than the quick sort. Essentially you're saying that I can't do ... what I did. Now, you didn't say "fastest comparison sorting algorithm." Arguably the radix sort is in a different class in that it's not comparing the values directly against the others. But that's not the point: the data ends up sorted, and in 1/5 the time of what you're saying is the fastest theoretically possible method. Somebody said that it couldn’t be done But he with a chuckle replied That “maybe it couldn’t,” but he would be one Who wouldn’t say so till he’d tried. So he buckled right in with the trace of a grin On his face. If he worried he hid it. He started to sing as he tackled the thing That couldn’t be done, and he did it! I get a little weary of people who say things can't be done. I've already done so many things that can't be done.

[@umairkhancis]

Very True @Argle @Gaurav your videos are great but may be this needs a little review because as @Argle mentioned Counting Sort or Radix Sort are on a different model of computation i.e Direct Access Array Model in contrast with comparison model of computation. What you mentioned in your video that Counting Sort and Radix Sort due to big range can take effectively NlogN time but representing numbers in tuple format to minimize the range of keys and then sort them using Direct Access Array Paradigm will effectively make it O(N) - in my understanding! Multiple passes of sorting tuples is a constant factor because we can know how many passes we will require for the given array. I think this topic/claim demands an in-depth follow up video, what do you think? Lecture from MIT 6.006 would definitely help here! kzbin.info/www/bejne/r5_HmHx6hJWth7M

[@codewithshareef]

Time complexity is regardless of processors, so the trick doesn't matter and should not be mentioned. Please correct me if I am wrong

[@Lastmomenttuitions]

great video bro

[@gkcs]

Thanks!

[@zyansheep]

O(N) time complexity? Easy. Let me present Quantum Bogosort: First randomize the list. Check if the list is sorted. If not sorted, delete the universe. In a parallel universe, the list will be sorted.

[@nou4605]

Just do the randomize in infinite parallel universes and pick the one that is sorted.

[@reethikavanaparthy6984]

I didn't ever thought of this concept....tq for making such a good video and sharing

[@poosaipandiv4947]

Do you understand this concept?ok tell which is fastest sorting algorithm?

[@amritaanshnarain7524]

@@poosaipandiv4947 Counting Sort.

[@Bouroski1]

O(N) sort is possible, ex : Unsorted list is (6,9,1,7) read value of first item : 6 Write 6 in 6th item of sorted list. read value of 2nd item : 9 Write 9 in 9th item of sorted list. read value of 3rd item : 1 Write 1 in 1rst item of sorted list. read value of 4th item : 7 Write 7 in 7th item of sorted list. Sorted list is (1,,,,,6,7,,9) Then you have a sorted list in 1 iteration, 4 operations for 4 items, and would be 1000 operations for 1000 items.

[@BryanDieudonne]

I love the content! Thank you!

[@CharlieForEve]

(1) He's saying that it takes at least log(the number of possible outputs) for any algorithm for any function. What is known about this? Has this been verified for many algorithms e.g. the surprisingly super fast ones? (2) Can you really treat all algorithms/problems as calculating each part of the output in sequence? For this problem, we could start by calculating the min and max (the min might always be 0.) That gives information on all values - does part of the work. This is not sequentially determining each position.

[@AnandGarg1994]

Bro this clickbait was not needed. This overshadows your quality content

[@tomasbohorquez2461]

I can't believe I was click baited by a Computer Science video

[@gkcs]

Hahaha!

[@Ownage4lif31]

Tomas Bohorquez ye same xD

[@gkcs]

Hey everyone! This video is meant to explain why O(n) is impossible for a sorting algorithm. I try to keep metadata as relevant as possible, but I have to acknowledge market realities. The titles have to be catchy and we all love drama. Thanks for all your feedback. Cheers!

[@keshavlakhotia1432]

Gaurav, i didn't get that part of god at 5:18 , i think you mixed two N's Like first u said if N is the single number u need logN time to say it to god , then after some time u mixed that logN with the original N i.e. number of elements in an array . Isn't it??

[@gkcs]

Yes, but they are the same in this case. When we choose an element to put into the sorted array, we are effectively telling God an index from the original array. This index can take values from 0 to N-1, which is N choices. So we need to say a number upto N, which takes log(N) time. And this number N is equal to the number of elements in the array. Once a element is removed, we have N - 1 choices, and God can now be told any number between 0 to N-2 to place in the second position. This requires log(N-1) time. And so on.

[@keshavlakhotia1432]

@@gkcs Ok, so just like insertion sort but rather than iterating for that min/max value god will help us , nice!!

[@gkcs]

Yup!

[@5nine838]

Hey , can u plz explain or share source why radix sort is not of order n , and what about bucket sort

[@Happymejoyus]

Thank you very much Gaurav, I was surfing for this and you gave the best concise explanation. Cheers to your efforts behind this!

[@gkcs]

Thank you!

[@Aditya-us5gj]

so it's something like as we can't travel at O(speed of light) similarly we can't sort an algorithm with complexity less than O(nlog(n)) 😁😁

[@gkcs]

I made a supposedly "clickbait" video on this. So I took another dig at it 😛

[@Aditya-us5gj]

@@gkcs hahaha u r simply amazing !!

[@rohitsinghgautam]

I just wrote a sorting suit and to compare fastest algorithm. Insertion sort is fast only if you avoid one of extra comparison, each comparison matters. Quick sort perform well for sorted reverse sort was slowest, it can be easily to workaround to make it fastest soft, this added one addition comparison in each iteration, but overall performance is excellent.

[@tthtlc]

Yes, many different algorithms all can given O(n) performance in the "best case" scenario as listed out here: en.wikipedia.org/wiki/Sorting_algorithm but most of the time, this is not achievable. So best we can get is average performance, which is usually worst than O(n).

[@mehulkumar3469]

It's not a clickbait he really sorted our concepts very fast

[@vinnieworks1854]

That was me when I learnt sorting yrs ago lol “ why are we learning this?”

[@vinit472]

Parallel logN parallel processes will sort the array in N time but again merging the solution will require logN time. Hence we can not have N runtime complexity for sorting. On the other hand NlogN is the best or average case not for worst case.

[@sterinsaji4513]

Why are we learning this hehehe😂😂😂thug life

[@victorduvanenko9291]

The flaw in the argument is exposed with an example of sorting an array of 32-bit floating-point numbers. Each element of the array is always 32-bits, whereas the array size changes depending on the number of elements in the array - this is the N in the O(N). The element size of 32-bits, call it M, has no connection to the array size of N. We can sort an array of 20 elements (N = 20) or an array of 20 billion elements (N = 20 billion). In each case, the element size is 32-bits. The number of digits in the index of an array is irrelevant, as an index operation is O(1) on modern computers - e.g., my_array[i] operation is done in one instruction, and is not done digit-by-digit of the index. Radix Sort is O(N) in terms of the size of the array itself. However, it is O(N * logM), where logM is log of the size of each element. The size of each element is considered constant, relative to the size of the array. Therefore, logM is considered constant, relative to the size of the array - i.e. constant relative to N. Since M is much smaller than N - i.e. logM is very small. For example, when using 8-bit digits, logM = 4, as there are four 8-bit digits within a 32-bit floating-point number.

[@onpoint1260]

it was just 13th second and you earned my like, well nice content, thanks for sharing

[@gkcs]

Thank you!

[@maxithewoowoo]

I think in a lot of time complexity analysis, comparing numbers is assumed to be O(1). Technically it depends on the number of digits but all integers are 32 digits so it's still constant time. And yet even when we make number comparison O(1) we still can't achieve faster than O(NlogN)

[@gkcs]

True.

[@T33K3SS3LCH3N]

The true O(1) sort is Intelligent Design Sort: assume the list was created by an almighty creator and is therefore already perfect as it is. Done.

[@JonatasCorreia]

The joke at the beginning of the video was enough for me to hit the like button. 😂 Congrats! Excellent content as aways. I love your videos. 👏

[@sabriath]

O(n) can be achieved.....a random number generator is created and seeded randomly, using that, the full set of the sort can be unraveled in order based on the seed cycle. Destroy all universes that are wrong, and we're done.

[@gkcs]

That's interesting! Of course, only if we can destroy all the universes in O(n) or lesser...

[@bhaswanthgudimella344]

Didn't get it could please explain it more specifically if possible with a short example

[@liviume918]

Count sort is O(n) if the size of input array is comparable to the range of its elements. Your computation is valid however if we add the limitation of not allocating extra memory.

[@creative-freedom]

Big-O notations always represent the algorithmic complexity. Putting in more hardware is outside its scope and can never ever be related to the speed of an algorithm. Hardware complexities considerations are called theta notations, as far as I remember! Eitherways, cool explanation!

[@gkcs]

That's true 🙂

[@carlavirhuez4785]

Oh my god! So clear and easy! Thank you very much!!

[@mattzahara9310]

You may achieve O(n) time if you do not rely on a comparison based sort. Radix and bucket sort are both O(n) in time complexity. Technically they are O(n * log(n)). There is an important distinction to make though. With merge sort and quick sort, the base of the logarithm is 2, while the base of the big O notation described previously is base 10. This is important because in big O analysis, constant factors are essentially ignored. Therefore the log(n), read "log base 10 of n", is ignored in the runtime analysis, giving you a runtime of O(n). This is a short explanation, but please to not listen to this man. Runtime analysis always refers to a single processor, ignoring cock speed and core count. This is because these factors will improve all performance across the board, and runtime analysis, specifically big O runtime analysis, is interested in the worst case running time of an algorithm.

[@itsjustboarsley]

Top comment material.

[@bogdanstankovic3022]

Gotta love that "cock speed" and the big O. Otherwise a good comment :).

[@angelowentzler9961]

log(n), no matter the base, is not a constant, therefore NOT ignored. The actual base of the log IS irrelevant, since logA(n) = C*logB(n) for some constant C depending on the values of A and B (eg. log(a) = 2.303*ln(a)). When you have polynomial complexity, lower powers than the highest in the polynomial are irrelevant. eg N^3+N^2 boils down to N^3, which is why we speak of O(nlog(n)) rather than O(nlog(n)+n+C). Under no circumstance can you say O(nlog(n)) boils down to O(n)

[@isanbothra5258]

I did not get your point.. what do you mean by "minimum time required to say any number is log(n)" as it contains log(n) + 1 digits?

[@editpapa9671]

Me : don't even know how to use while loop properly Watching ** fastest sorting method**

[@Patrickhh69]

Worstsort is the fastest scoring algorithm, if you set f(n)=D^n (n) where D() is the loader function and the base sort at bogobogosort

[@ShankhaShubhra]

Did i just watch a 9 min video just to get trolled at the end? ☹️

[@Market_Majnu]

Nice way sir u driven out the technique to learn with fun

[@ezpz4akash]

State Space Search To Prove This! Awesome 🤘

[@JohnSmith-ut5th]

Let's be clear linear or even constant time sorting *is* possible, however, this is at the expense of accuracy or range. The best case for the general sorting problem is O(n log n). However, nothing we do on computers is actually general case, so there are no theoretical limits on what can be done on actual computers. When we examine worst case time complexity we are talking about theoretical limits on theoretical machines. I'm not saying it is not useful. It is extremely useful, but we also have to understand what it actually means.

[@PRIMEVAL543]

0:07 am I racist or are they all the same guy? XDD

[@gkcs]

Hey, that's racist! 😂

[@anirudhmenon749]

For those wondering why log (n!) = n log (n), heres why- log(n!) = log (n * (n-1) * (n-2) * (n-3) ... 2 * 1) = log(n) + log(n-1) + log(n-2) + ... + log (2) + log (1) = n log n

[@toniokettner4821]

nothing proven here and the equals sign is also wrong.

[@vishalchauhan9832]

Awesome intro and Amazing lecture sir !

[@GabrielsEpicLifeofGoals]

Radix sort is O(d) where d is the amount of digits in the array.

[@shikharsharma02]

Video was awesome, But stop putting deceptive title. You may lose the faith of your students(subscribers). Content was great!!

[@davidjames1684]

Counting sort wins for a small range of possible values and can also be modified for large range of sparse values by using an order preserving hash function.