Big O myths busted! (Time complexity is complicated)
HTML-код
- Опубликовано: 2 июн 2024
- Is O(log n) better than O(n)? In this video we talk about algorithms, time complexity, and why it's sometimes confusing.
Buy 🦀 Rust stickers: strager.net/booty
00:00 what is the best algorithm?
00:16 locating errors
01:28 benchmarking the naïve algorithm
02:08 analyzing the naïve algorithm
04:33 the line tables algorithm
05:44 benchmarking the line tables
08:06 a fair comparison
09:48 binary search
10:43 analyzing binary search
12:49 benchmarking binary search
14:28 coding SIMD
18:34 pop quiz answers
Thanks:
Jennipuff: / jenipuff
Attribution:
Thumbnail artwork and photography by Jennipuff
Sound effects: pixabay.com/sound-effects/sfx... pixabay.com/sound-effects/car... 
Наука
![KFF Singapore Badminton Open 2024 | He/Ren (CHN) vs. Alfian/Ardianto (INA) [7] | F](http://i.ytimg.com/vi/an7AykjOaAA/mqdefault.jpg)
Source code of all of the techniques (for educational purposes):
github.com/strager/big-oh-lines
Corrections:
19:23 I show vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 12, 12, 12, ...], But this is incorrect. The Vec items should be line numbers, not offsets. (The keys are the offsets!) So the Vec would actually look like this: vec![1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, ...]. (Thanks to @polyfoxgames9006 for pointing this out.)
Pop quizzes:
04:24 average time complexity? answer at 18:34
09:42 another way to preprocess? answer at 19:09
12:23 why does binary search 2x? answer at 20:14
14:17 time complexity of SIMD algo? answer at 20:47
Lessons:
01:13 1: Try it!
03:28 2: Check your loop bounds
03:46 3: Stress test your algorithms
06:09 4: Big O is not the full story
07:42 5: O(n) ≠ O(L)
09:17 6: Preprocess your data
12:09 7: Big O is approximate
13:53 8: Big O is for big inputs
17:44 9: SIMD is awesome
I think that you should mention that big O notation really is really nothing more than a set of functions of a "certain shape", and that the shape of your expression measuring what you want (running time, space complexity, number of steps etc.) is in that set if it is asymptotically dominated by functions in that set.
More importantly, I think it is quite harmful to bring up the notion of the average case runtime for a deterministic algorithm over a distribution of inputs as if it is says anything meaningful - since how do you define the input distribution, and what does it tell you? Nothing at all for a deterministic algorithm.
You can flip the picture and consider an algorithm like the one you describe but where its input is considered a cyclical buffer (just start over when you reach the end...). Then you could have it pick an index uniformly at random and do average case analysis based on the random choice. This is a good example of both probabilistic analysis of running time and of the advantages of a randomized algorithm.
> I think that you should mention that big O notation really is really nothing more than
Plenty of other videos explain it this way. I wanted to explain it a different way which I think is more intuitive.
> I think it is quite harmful to bring up the notion of the average case runtime for a deterministic algorithm
I brought up average time complexity after talking about best and worst case. I wanted to show that, given a best case of O(1) and worst case of O(n), average case is *not* necessarily 'in the middle' of best and worst. Average case time complexity was not O(n/2) or O(sqrt(n)) or something; it was just O(n).
@@strager_ But wait, O(n/2)=O(n). I think intuition is fine, but I think it's important to mention that that it is not the whole picture.
Regarding your use of average case analysis, my point is that, sure, you can perform a thought experiment - but I think it is important to mention that it only has any merits when comparing algorithms w.r.t. a "meaningful" distribution and that it is very hard to define. My concern would be that viewers would be inclined to use uniform distributions over input spaces when they see it done this way when this is not mentioned. Anyways, take it for what it's worth. People seem to like your video, and so do I.
I'm primarily specialized in graphics programming & self taught. Got major ADD issues, and can't even remember the months cuz what's the point?
Your formatting is perfect. It keeps me entertained, and you're good at speaking, all while teaching and representing ideas in simple ways (: sick af dawg, dis gnarly.
> I think it is important to mention that it only has any merits when comparing algorithms w.r.t. a "meaningful" distribution and that it is very hard to define.
Agreed. I didn't make that nuance clear in my video.
Big O is not bad nor a lie, you just have to understand it. It does not tell you how fast an algorithm is. It only tells you how it scales with respect to its input size
Yea, it took me a moment to understand what he was saying in the screen shot, since it never dawned on me that anyone had ever believed the simplified (and therefore incorrect) "myth" as he was using it.
The whole video is a strawman take on Big O. Debunking and correcting claims nobody actually believes, and if they do, they are misunderstanding it.
this video proves that youtube is full of people that teaches from ignorance.
C'mon guys, everyone uses some way to lure people to watch their video.
All in all, great video! A lot can be learned from this video, I think you'd be a great teacher if you aren't already.
@@Meneer456 yeah, why people so toxic and calling him strawman huh? bad day? Why dont you get in front of a camera, lets see how that goes.
The biggest thing to take away is that big O is not equivalent to the actual performance, it is an upper bound for the growth rate of an algorithm. When comparing algorithms look at the behavior when you double the amount of input.
Usually it becomes way more obvious if you decuple it instead of just doubling it 😅.
yea everyone seems to forget this
Isn't that the entire point of big O lol how could anyone forget this
@@tear728 they never actually learn what it is
@@tear728 I can't remember who it was but I recently saw a video where someone said they almost failed their Google interview because *the interviewer* didn't understand this. The question was something like "Algorithm A runs in O(n), algorithm B runs in O(logn). What's faster?" They correctly answered that B is better asymptotically but A might be faster for small inputs, and the interviewer insisted that was wrong.
This is like how they discovered a new “efficient” multiplication algorithm for large numbers but the constants are so huge it’s only faster once you’re multiplying numbers over 4.5 trillion bits long
Yup! Luckily, I haven't needed to deal with data sizes that big. 😅
Yup. Those "galactic algorithms", as theyre called, dont really have any direct real world use; they however are useful for the theortical part of computer science such as by showing that certain bounds can be broken, or by giving a framework of techniques by which practical algorithms can be newly developed or improved further. Theres also the chance that at one point well have to deal with such huge inputs, but as with abstract mathematics the usual way they become useful is by laying the groundworks.
@@RepChris probably if you want to have highly accurate (as accurate as Quantum Physics let's you be) Physics simulations, these can be useful
@@kuhluhOG Yeah, but that falls under the "we might get to that amount of input data at some point" category, as we currently very much do not use even remotely the amount of input in any application to make a galactic algorithm faster; that is somewhat tautological since thats a part of the definition of what a galactic algorithm even is.
@@RepChris it was more of a comment on your sentence "Theres also the chance that at one point well have to deal with such huge inputs"
It's important to keep in mind that Big O is for classifying the scalability of algorithms, not their performance in a given context. Big O analysis is not always a substitute for a benchmark.
When I got taught big O at the university, many people (including me) failed to comprehend the actual meaning of it (some still don't). One could replace, like, 2 lectures worth of material with this one video. Keep up the good work!
Thanks!
I personally always found O notation one of the easiest things in theoretical computer science.
at our uni we weren't even taught what big O actually means (what is explained in this video), instead we were taught to blindly follow all the myths...
The easiest way to understand big O in my opinion is to not just focus on the most significant term, but rather write out the entire time complexity, so instead of O(n^2) it'll be something like 4n^2+80n+20n*ln(n)+35. That kinda helps understand that the constants do matter and can overpower the n and which term is the most significant for a given n. Like O(n) isn't better than O(n^2) if O(n) is 8,000,000n and O(n^2) is n^2 unless n > 8,000,000.
Like take this scenario, you have some counting function that relies on sorting and it's O(n*ln(n)), is it worth the effort in switching to a priority queue to get that O(n)? That depends on what you expect n to be. If this stuff will involve at most a thousand items, probably not unless there's some serious time critically going on (which generally there won't be), if it's going to involve billions then yeah.
Big O notation says that, given a function f and a function g, where f(n) is in O(g(n)), there exists some constants c and k such that f(n)≤c*g(n) for all n>k. I never found it hard to understand or formalize, but I can see why it seems hard to understand. In general, big O notation only matters when you have differing time complexities and large values of n. It tells you that, as n grows larger, a function that is not in O(g(n)) is going to necessarily be larger than a function that is in O(g(n)).
This is one of the greatest programming channels, keep up the good work!
The greatest
Every person I've seen using comic sans in a presentation is an absolute beast. Like you have to earn your right to use it.
@wernersmidt3298 It's an honor to be compared to Simon Peyton Jones!
@@strager_ So... are you gonna make a Monad tutorial next? 🙃
One of, if not the best big O notation video out there. Bravo and thank you!
This channel is pure gold. Clear explanations, starting from simple problems and going to more sophisticated ones, step by step, while not focusing on little details for too long and constantly tossing in some new questions for viewer to think about. Thanks for your effort
And zero content fluff!
O notation might be for big data but different O complexities have different Ns that count as big. N=50000 may not matter for difference between O(N log N) and O(N log log N) but it is big enough to make a difference for O(N^2).
I still have PTSD from times when I spent hours upon hours waiting for my Windows to update because someone in Microsoft deep down the history decided that number of updates will never be big and used some kind of bubblesort to sort them.
> different Ns that count as big
Agreed! But the notation doesn't give you *any* clue where this point might be.
Actually, there are still some places in Windows like this, that someone have 10 minutes opening Start menu in some conditions. Or Explorer starting to slow down when doing something like deletion in a folder with thousands of files. (Explorer meaning desktop as well.)
You know, I think it's dumb they used bubble sort (at least use insertion sort!), but I really have to wonder how many updates you missed if bubble sort was enough to slow down the time to update significantly.
Wanna hear the best thing? It's Levin's universal search. It can solve any computable problem in an optimal time complexity. The only downside? The universal search adds a constant element which scales exponentially with the length of the optimal program. If the optimal program is L bits long and achieves O(f(n)) time complexity, Levin's universal search will achieve O(f(n)) time complexity, but with an added 2^L cycle delay. This delay quickly gets absurd, so the universal search has no practical application.
Gotta love ivory tower computer scientists!
The reason you don't need the log base is because you can convert any log to any other log using a constant factor - which is ignored in the O-notation.
log_e(t) = log_2(t) / log_2(e)
log_2(e) is a constant. In O-notation, log_2(t) and log_2(t)/C are the same, which means log_2(t) and log_e(t) are the same.
my favorite "non linear" algorithm is manipulations within the Disjoint-set data structure - it has an average and worst case of O(a(n)) where a is the inverse Ackermann function -- functionally less than 5 for any number you can write.
Wow that's amazing hahaha. At that point it may as well be constant time. But no, an infinite input size will have an infinite lookup time. Incredible.
I think they use the inverse ackermann function for amortized analysis which basically just treats it as a constant :)
Great explanation!
One aspect that isn't talked about much is that due to laws of physics the actual *random* access time (in seconds) to a pre-computed table of size n is O(sqrt(n)), not O(1). As a result there are algorithms that are actually slower in real time for large inputs even though they are predicted to be faster by big-O.
There's a great article called "The myth of RAM" that explains it deeply.
In modern computers, are cache effects what you mean by sqrt(n)?
The simplicity of RAM (Random Access Machine) which we normally use for complexity analysis is indeed deceiving. My case study didn't lend itself to an explanation of RAM (or CPU caches), so I kept it simple and focused on other issues with time complexity.
@@strager_ yes, it's cache but the article I mentioned explains it can't be fixed by making cache bigger because of quantum physics (maximum amount of information in black hole is proportional to its surface area and nothing can be denser).
And yes, I understand that this is introductory video so advanced stuff like this wouldn't fit in there.
If I understood that "great article" correct (I only had a quick view on it) the reason for that O(sqrt(n)) is that memory (RAM) is typically flat - so the double amount of memory needs the double area. If these area is a square when doubling the memory causes that the width of this square is increasing by factor SQRT(2) - and therefore the average physical distance the information has to "travel" is proportional to SQRT(2) of the size of the memory.
As information could not travel faster than the speed of light that really would mean that the access to memory is getting slower the larger the memory is....
On the other side transistor density on chips is still increasing - double memory therefore not mean that the double area is needed - that might will no longer true in the future but for the next years O(1) makes more sense than O(SQRT(n)) for memory access.
@@elkeospert9188 almost, circle is a better representation but when we use big-O we don't write constants, so we drop Pi.
The article has other parts, where the author explains that quantum physics dictates it will never be O(1) and stay O(sqrt(n)). Increased density of transistors helps only by a constant. If you need to process 100PB of data, you can't fit it into RAM and will need to use other storage which will be slower.
@@strager_ Even ignoring physics fundamentals, if you're using virtual memory the pagetable lookups are O(ln n) so the O(1) claim for lookup tables was always suspect. Of course caches - incl TLB - mitigate this in practice, so long as you fit within it.
I'm a physics PhD student who has to code all the time despite having taking very few formal courses on it. I find your videos super helpful and have been learning a lot!
Let me guess, fellow HEP enjoyer?
@@43chord cosmology :)
@@fireballs619 what do you do in cosmology?
@@mastershooter64 CMB analysis mostly
7:51 "[...] and, in fact, you have fewer lines than you have bytes"
A file containing only
always has one more line than bytes. In fact, an empty file has no bytes at all, but one (empty) line.
Factual.
Obligatory comment noting that in the manually unrolled loop, the code may reach outside of the array bounds, resulting in a crash, if you're lucky. This is still one of the best complexity explanations I've seen.
> the code may reach outside of the array bounds, resulting in a crash
Yes, that is true. I didn't explain this in the video, but when generating the table, I added 7 dummy elements to prevent out-of-bounds issues. github.com/strager/big-oh-lines/blob/537e6a048d10c89ee6ea421c48c4ecc7229d2d01/bol_linelinear8/src/lib.rs#L24-L26
@@strager_ alternatively you can just modulus the SIMD size, and do the non-SIMD naive stuff on the remainder, if you don't want to do array resizing nonsense
Hey while we are traversing through the string, as soon as we hit a
char we can store a counter which increments for every line and if we want to show the line number just use the counter variable which will not take any time
definetly possible, but usually in compilers there is a single pre processing step before the representation of the code changes. Compile time errors, as far as I know, are usually not found until the second step of compilation
> we can store a counter which increments for every line
That is true, but in the real world it's usually more complicated than that.
Context: A compiler in practice does not always report errors immediately. It might need to parse some code then report an error in the past. (For example, Rust cannot report a use-of-undeclared-function error until it reads the entire file because the function might be declared after the call.) Therefore the compiler needs to attach location information to each token and AST node.
In addition to line information, a compiler also wants to report column information. The compiler *could* attach two numbers (line and column) to each token and AST node. But some IDEs want byte offsets, so we might need to store three numbers (line, column, and offset from beginning). That's a non-trivial amount of data to add to *every* token and AST node, so memory usage goes up.
To reduce memory usage, a compiler could attach only *one* number (offset) to each token and AST node, and compute the line number and column number as needed. (Or not compute anything if the IDE just needs a byte offset.) Hence the table-based solutions discussed in the video.
But that's for a traditional batch compiler. Nowadays compilers are integrated into editors. Compilers are given *updates*. LSP (Language Server Protocol) updates communicate line and column information *into* the compiler. Having the line table data structure makes this operation much cheaper.
I didn't discuss any of this in the video because I didn't want to bore people who aren't interested in compiler frontends. But it's a good discussion. =]
Fantastic presentation and explanation! Although I watched you put this together, seeing the final version was even more engaging than I expected. Great work and thank you!
Dude showing the y=mx+b and the graph and then showing in as o(n) shattered my brain. That makes so much sense.
Thanks for this Amazing Video!! I am a fan of your channel, and love the kind of content you have been putting out recently Its really good to see you uploading more often, cant wait to see what you share with us next!
Didn't learn anything new about Big O, though the reminder is nice. What I did learn, though, was how easy it actually is to use SIMD, at least for simple applications like this.
I've tried looking into it in the past and just got super confused.
I have to say, a video specifically on SIMD would be awesome.
> a video specifically on SIMD would be awesome.
My previous video on hash tables also contained some SIMD stuff. That hash table SIMD was more advanced, but I didn't walk through the code. ruclips.net/video/DMQ_HcNSOAI/видео.html
I do want to share more SIMD knowledge in future videos. 👍
The portable SIMD struct that nightly rust has is awesome.
@@Dorumin yeah, intel should've named the vbroadcast intructions "splat" instead lol
@@treelibrarian7618 I was talking more about the structured approach to lanes and its ops over intrinsic instructions on small buffers, plus the nice Into/Froms. The names are funny though, what do you think about the swizzle trait? :P
@@strager_ I would love to see it, something I'm very interested in learning more about
Certified strager classic.
Wow, I’m actually planning on optimizing a batch processing API for tomorrow and I came across this video. Learned new insights that will help me make decisions on optimization. Thank you for this! 🙌
I met you on twitch and you even helped me with a terrible code that I wrote, I already knew you were like a genius but what you are doing on this youtube channel surpasses everything!
Loved your ending! Take that, Rust Foundation! :) Thank you for the Big O lesson as well.
Really loving the past few videos. Learned a ton. Thanks.
Mate, you've got the nack for educating. I'm loving the channel.
Really love your optimization videos and the way you explain. Keep it up my man!
This was an absolute treat to find in my notifications after work. Thank you
I am so glad I found you from your hash table video. Concise, informative content, with proper suggestions and pop quizzes to keep the viewer entertained. What more could you ever want?!
An extra thicc rust crab sticker, probably
Man, that's one of the most succinct, best explanations I've heard. Keep posting!!!
Thank you for the helpful information learning these subject alone sometimes feel depress but watching contents like this gives me hope thank you again!!
Having started ThePrimeagen’s course on Algorithms & Data Structures, this was a a pleasant addition for me.
.
I like that you did a pop quiz ‘before’ the material. This follows the research of learning effectively as described by Make it Stick and other books.
.
👏👏👏
This week I learned ways to optimize if-statements in Bash Scripts for a CPU prefetcher-unit’s performance, and about misprediction penalties for the branch-priority features.
.
And I’ve only started learning to script/code/program for a couple months.
.
I’m so grateful for the efforts being out into maintaining and contributing via the internet so I could access all this! Whoo Hoo! 🤠
That is so good, super clear and super interesting ! Love your work
These are some good informational videos. I really like the fast paced nature of them, focused on the question at hand. I feel I can learn in 20 mins what would take me a few hours of watching some other videos.
This is probably the most helpful time complexity video I've watched to date (and I've watched a lot). Thanks so much.
I love the build up of information and background of a problem.
This was randomly recommended to me, and it was one of the best explanations on big O I've seen
I love your videos, your explanation is straight forward and comprehensive.
Everytime I watch your vid, everytime I get a tons of insights from you.
Thanks and please keep going!
Interesting stuff. Thank you for demystifying some of these concepts.
For the array lookup, wouldn't you store the line number at each position not the offset?
You're right! I messed up the explanation. 🤦♀️
Big O is meant for describing limiting behaviour as it reaches infinity. We never use infinite elements. So there are plenty of algorithms that could have worse Big O notation and be faster because we use fewer elements. I personally never liked Big O notation in Computer Science because it often detracts from practical algorithms. Nice presentation.
On computers, it's really difficult to know what will speed something up sometimes :)
Big O is also meant to describe worst case scenarios. Maybe the worst case is vanishingly rare for your particular use case, so optimizing for Big O might not lead to any speed improvements. Context matters!
At best, Big O can be used as a guidance, but should never replace real analysis and measurements on actual real world data. You lose so much information about an algorithm by trying to describe it with just a few symbols.
@@oscarfriberg7661 even in that case, it's specifically for the case where the input/problem size is sufficiently large
@@shiinondogewalker2809 people who complain about big O's practical value often have no understanding what it means. Big O doesn't need anything in your program to go to infinity. The information it gives you becomes true for input size above N, what N is, depends on your formula. Could be 10, could be 10^10.
People who think "it only matters for infinite value" remind me of debacle at Microsoft, some "practical programmers" who thought the number of updates will never be "sufficiently large" so they used the wrong sort algorithm leading to millions of people waiting hours, days for windows updates 😂
@@oscarfriberg7661 big O tells you the upper bound, while big Omega telling you the lower bound. So any argument against big O citing worst case scenario could be reverted into argument for big Omega, now you optimize for lower bound, for large input your algorithm will always be at least as good as the value you optimize for :))
And to many people big O and big Omega and big theta are all "Big O notations", so when they spout "Big O are useless" they mean any asymptotic notations.
"Big O notation in Computer Science because it often detracts from practical algorithms"
Big O detracts from practical algorithms the same way the ability to count detracts from practical algorithm
There are two stages when you design an algorithm
the theory stage, where you use reasonings in discrete mathematics to derive the right computation then formally prove the time/space complexity (if you skip this stage it's because some smart person already did it for you and wrote it in a textbooks/papers somewhere then other people repeat it into wisdom and eventually it reaches you without you having to open a textbook).
And the implementation stage, where you take into account what the compiler does, what the CPU does.
Big O doesn't care about algorithm or its implementation, it cares about functions f(n), g(n) on (typically) natural numbers. It is a mathematical concept, much like counting, both deal with natural numbers, and both are used to estimate.
Now guess which stage are big O and counting more often used in :))
Probably stage 1, but it does help in stage 2 too, it gives you a direction on which practical things to try when you don't have all the technical details of your machine, what kind of optimization is done on your CPU etc.
because in practice, you don't start out knowing all these technical details. If you already knew like in this video, what kind of sampling distribution your input data have, how fast your algorithm runs on this specific CPU, then why would you go back to look at the more general idea which makes no such assumption about your system? if the aim is to disprove the theory using practical implementation I suggest at least understand the theory first. e.g. big O never implies O(log N) is faster than O(N^2), that's stupid, an algorithm in O(1) is also in O(N^2)...
Or of course you could spend time running your algorithm on billion different input sizes, that's very practical too :))
Now do I need someone who is good at discrete math and algorithm on my team? no I don't. Do I want someone who doesn't understand the basics such as what big O notations tell you... absolutely not, that's a recipe for disaster.
Excellent video! I found it to be perfectly balanced in terms of explanation, providing just the right amount of clarity without becoming overly lengthy or tedious.
I've followed the making of on Twitch. Glad this is out!
I love the presentation, and I also love the dratini shirt
Really good video! I found this explanation of big o a little unconventional but good. I especially enjoyed your visuals and your dive into SIMD at the end. Thanks!
Best big O notation i ever watched, thank you very much. ❤
This video is an excellent explanation of Big O notation and what it really means for our algorithms. Great stuff here!
Your tone and editing make this comfy.
Excellent video!
About leaving out the logarith base, you do it because changing the base only changes the function by a constant factor.
In my experience Big O is very rarely a useful metric in web frontend code, since frontend deals mostly with interactivity the number of "things" is relatively small and low latency and minimising network traffic is almost always more important than number crunching efficiency. In fact for almost all DOM related things; if the number of objects is even barely approaching a size large enough for Big O to be meaningful; the DOM tree is probably so large it will kill most mobile browsers for excessive memory use. Also since your code runs on any random client you don't control how fast it's hardware is so most number crunching is better done on the server (in which case it's the backend developers problem 😉)
This is a great point!
This is the best introductions to Big O I've ever seen or read. Thankyou.
This video was awesome! Thank you so much for the great info, I learned a lot.
Wow, this is as clear, concise, and comprehensive as I could imagine!
The past two videos have been great!
This is EXCELLENT! Thank for the information.
Totally agree, the best channel I bumped into in years!
As a CS student, I truly appreciate this way of explaining theorethical computer science. Thank you so much!
I was expecting to see SIMD binary search :D
But the video is a great refresher, thanks for it!
Love your videos. I learn so much!
thanks for making this video, helped me remember a lot of useful stuff from university ^^
As someone with a background in mathematics, this was all... kind of trivial to me. But I see misconceptions about big O notation all the time from programmers so I can imagine this being very much needed. It's really just about limiting behavior, the same tricks mathematicians use to tame infinities, divisions by zero, and all that. It feels absolutely absurd to say it... but the actual specifics of implementation, and real world performance metrics are FAR more important than a cool mathematical trick used for shenangians. Anyway, very good video, and a very needed one to try to push against the absurd hyperfocus on big O time complexity over more relevant discussions about overheads and actual implementation.
That misconception comes from the theoretical CS community. They talk only O(.), all the time.
For good reasons, but it's also -in no small part- arrogance.
Similar thing with pure vs. applied mathematicians.
I remember there was someone who also made a video about how they were frowned upon by an interviewer for mentioning that Big O is just about how algorithms scales and not comparing how they perform in all cases. It shocked me because it seems almost common knowledge.
Wow. Amazing video! Good stuff!
U earned a subscriber!!🤟🔥🔥
Keep growing!!😊
Amazing dude.... how do you make those graphics? In case you use Adobe Premiere or any other editing software for it... what software do you recommend for drawing graphics like it?
I used Microsoft PowerPoint and Motion Canvas.
I love PowerPoint. I'm new to on Motion Canvas.
Extremely informative and intuitive presentation. Thank you! :)
However, I'll admit I'm not as familiar with SIMD stuff, so the speed at which that was moved through left me with some questions.
Will probably look into that on my own, but I would love to see something on that if it is a topic you'd want to cover in the future too!
> the speed at which that was moved through left me with some questions.
Thanks for the feedback!
I love you man, keep on uploading please
Super interesting, thanks for sharing!
Just found your channel and I'm hooked.
I really like how this video explains how better big O doesn't necessarily mean better performance for data one's working with, while at the same time it doesn't overdramatise things. As video states, big O describes the general shape of performance curve with increased data, but it isn't be all and end all. And as SIMD example shows, even if it has the exact same big O parameters as line table, it makes up for it with what I call "small c", i.e. those "insignificant" constant factors like the slope.
Personally, my intuition is to prefer structures and algorithms with better big O parameters for key operations - the idea being that for most scenarios either the data is so small extra constant costs are negligible, or the data is so big that better big O matters. But like most things, it's not an absolute rule and in the end, it takes real life performance testing to get the most complete picture.
Really good video. Thank you!
this was a really smart way of making me watch a video on big O notation nice job
I must admit I found your explanation very straightforward and easy to understand.
You got a new subscriber, fantastically informative video ty sir
Hope for more video coming on RUclips, really appreciate them 😊
the base of the logarithm doesn't matter because it is just a multiple and we are already omitting coefficient!
also as a mathematician I would have loved to see Landau's Big-O notation in its actual form.
we say that f(x) = O( g(x) ) as x -> ∞ if
there exists an M > 0 and an N > 0 such that
if n > N then f(x)
Yeah, I didn't explain clearly why we don't care about the log base.
Great explanations !
I love how you use the shrimp emoji for the left arm muscle flex. Great video!
You are the first one to point this out! 💪😍🍤
Very lucid, admirable density :)
information quality over 9000! pure signal, no noise
Love this type of videos, please more :)
Creel has made a pretty nice video touching on the subject as well, regarding sorting algorithms.
This was a much better video than i expected
Really awesome video!
In java, the program still works when there are no new lines, meaning we could essentially write the entire program in one single line. I wonder how the compiler detects error in such case.
The compiler doesn't care. It'll just report all the errors being in line 1. It's the programmers problem to deal with that.
you usually get line & column information. once you know the line, you can just compute the column using some simple arithmetic (error_offset - line_begin + 1).
great channel, these are really interesting . Also why is it so rare for the compiler to optimise with SIMD instructions, are those comparison blocks just not a common code pattern?
> Also why is it so rare for the compiler to optimise with SIMD instructions
In this particular case, there are a few reasons why autovectorization is a problem:
* The compiler cannot reasonably assume that the Vec's length is a multiple of 8. Supporting any Vec is complicated.
* Because of the early return, and without profiling data, the compiler might think that it's common for the *first* element to return, therefore SIMD isn't worth it.
* The compiler is written by humans with limited time, so the autovectorizer is implemented for common code patterns. I suspect my algorithm isn't common. (Maybe it's common with '==', but not with '
great explanation :D
Title is a bit clickbaity but I really appreciate your channel. Not a lot of people go to the lengths you go to to help viewers(/readers) really see the thought process and the knowledge that contributes to it. These videos, like the best documentation and code comments, makes both 100% clear.
Thank you for making my day!
I know this was just educational, I know this was supposed to showcase Big O and different approaches to programming. BUT if I dont say this, I'll lose sleep over it so here goes. You can just increment a variable by 1 everytime you encounter a newline while compiling. So when it encounters an error, you have the line number ready. Time complexity O( time to reach error ), Space Complexity O(1). You are designing a compiler here, I'm sure you can add a line or two to the code can't you?
You would need to store that line number somewhere. Storing line+offset or line+column uses more memory than just storing the byte offset. That memory consumption is multiplied by every AST node, so it's actually O(n) space usage.
Also, the line tables I describe in the video are handy for implementing LSP.
these videos are great!
fantastic video. subscribed
Thanks for the interesting content!
I wish someone had explained it to me like this when I started my developer journey.
I didn't know there were misunderstandings about this topic. I guess my uni did a good job (thanks Prof. Schöning
7:14 even if you adjust the x-axis, you can't have a straight line because your x is discreet. You can't have 1.5 lines, so it would be be jumps as well.
Yeah, I should have made it a scatter plot. Good point.
All software (algorithms) perform transformations on data structures: 1. Choose the correct data structure to distill your data (eg vectors vs hash tables). 2. Choose the correct algorithms to operate on your data (eg. for-loop vs binary search). 3. (Advanced) Note which ones work best toward your design goals.
Thanks a lot, men. Your videos are very useful.