What Is Big O? (Comparing Algorithms)
Vložit
- čas přidán 5. 09. 2024
- With so many ways to solve a problem, how do we know which was is the right one? Let's look at one of the most common methods for analyzing algorithms: Big O Notation.
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Brandon Chen, Elaine Chang, Zachary Greenberg
Twitter: / ubehavior
-
Extra Resources:
Big O Wiki: en.wikipedia.o...
Analysis of Algorithms: en.wikipedia.o...
Time Complexity: en.wikipedia.o...
Sorting: en.wikipedia.o...
Fast Inverse Square Root: en.wikipedia.o...
Picture Credits:
s-media-cache-...
Actually I had a hard time wrapping my head around these concepts. But the metaphors used in the videos were so good, in fact it was very fascinating. Thanks for explaining this in a very interesting manner.
Listen man....this video was awesome!! and it totally deserves more than 150k views. Your examples were just amazing....they flipped switches in my brain so thank you!!
Searched for Big O, came for the pokemon
stayed for the pokemon?
it's "came for big O, stayed for the Pokemon"
If you already kind-of-not-quite-100% get Big O, the metaphors here are actually pretty good. If you're still confused about Big O I recommend looking at the limit definition/interpretation if you know what it means in calc. It's basically like when you learn limits- what happens when x gets really really big in f(x) compared to g(x).
Algorithms! Gotta understand 'em all!
This seems like a David Lynch film: hard to understand but many people like it anyway
it looks so professional but personally I didnt get a thing lol
0:38, I nearly had a stroke.
still no freaking clue what "O" is.. is it just there as a decoration? no clue...
Big O notation, also called Landau's symbol.
Landau's symbol comes from the name of the German number theoretician Edmund Landau who invented the notation. *The letter O is used because the rate of growth of a function is also called its 'order'.*
Props for including fast inverse square root!
this is literally the best video I have ever seen on the entire internet. thank you for this.
If at 6:44, the worst, average and best cases are all big-Ohs, then where does big-Theta and big-Omega fit?
Wow, the cutest video about Big-0 i've ever watched (pokemon). wished i understand other references as well
Another great video! I knew about the notation before, but you really nicely explained it to those that might be new to it. Keep it going! Unlike the other commenters, I think the analogies were on point, especially the train one.
This is a really great visualization of the Big O concept
I watched a bunch of big O videos because I just didn't get it from my lessons at uni. This is super understandable and actually fun. Thank you!!
That was brilliant. I don't come from a computer science background and this was the only video so far that clarified what big o is. Thank you. Have subscribed 😊
Great video! Also, I think it's absolutely hilarious that the analogy to ignoring scaling factors is that "we allow the algorithms to take performance enhancing drugs" lol
As the self-proclaimed owner-driver of a multi-level, self-adjusting feed-back loop (neural network?), I want to thank you for for the equivalent of a Vit B12 shot . Interesting how so many ''obvious' solutions only become 'obvious' AFTER they have been recognised /explained by a master. Well done, and Thank you.
Love these videos! Would love to see more CS and Algorithms explains this way =)
Thanks for this. I like that you're explaining it without even touching code. Mario and Harry Potter make for a better explanation than code.
This deserves more views.
Maybe it is because I already know the subject, but the metaphores at the start seemed quite confusing. Also the graph (turtle, car, train, Mario, ...) is a bit confusing. You have X axis called distance, and Y axis called time. But the function are in terms of N. That might be confusing to some.
Vojtěch Frič I agree, I feel like there must exist better ways to introduce this subject. I don't think this would have been all too clear for me if I was learning from this initially.
I didn't know any of this. This was as clear as I can think of (surely I don't understand it in any depth level but most ideas of CS to someone outside is to be kept at a ground level at first), I think you guys are suffering from overthinking, because you already know it. However, there are always quite some room to improvement, like the inverted axis. You can give it a push by just puting a note to remind of it, I only noticed it when you said that n² would take longer than n.
I was having a hard time understanding the topic until I watched this video. The examples were very helpful.
Or, to state that beginning "mess" of a definition in a graphical way:
1) Draw f(x) in a coordinate System.
2) Draw g(x) in the same system, but you can squish it as much as you want.
3) Look as far right as you want, starting from any arbitrary point that you want
4) f(x) is in O(g(x)) when f(x) never overtakes g(x) from said point onward
Thing that helped me understand this after many hours: the definition of big o ISN'T connected to effeciency of alghoritms itself, it explains how it works - you have 2 functions, one f one g, and on graph you clearly see that one (let's say f) at some point ends up under g. Now, no matter what you do to g without changing it's shape, so only moving and rotating around, if you go far enough it will overcome f at some point. And I was stuck here... what does it have to do with alghoritms??? The answer is that t(n), the time function of your alghoritm, likely a code, is interested in the worst case - the fact of going far enough to the right. To find out what would happen in such case, you can use O() that will give you the upper bound of possible time needed, since it makes the function go far to the right.
One more thing: it is obvious that your alghoritm won't always perform in the worst time, the O notation is used for things like hardware requirments, where you need to be prepared for worst. There's also less used average time based calculation.
To sum up, the O function kind of rates the shape of time function describing your alghoritm, or how it handles huge/tricky inputs
comp sci and pokemon. finally the youtube algo doing something right
I'm not sure if the racer analogy is that helpful for understanding Big O if you've never heard of if, but I personally found it pretty fascinating.
I've never thought about idea of linear time meaning constant speed and logarithmic time meaning constant acceleration.
Most straight forward video I have seen on Big O. Great job!
this is the best explanation of big O I have seen.
This is fantastic. Love the metaphors, it helps it be more tangible. Thanks for the video!
The n log n limit on sorting only applies for sorting algorithms that compare elements. For example, you can sort in linear time using radix or counting sort
very good explanation...if you don't get it here's an example:
g(x) = O(f(x)) means that f(x) has a longer execution time, the time it takes to finish.
In other words, any function that runs faster than f(x) will be O(f(x))
I only liked your comment because you can send it bro.
Thank u ☺️
very well explained with examples and graphics. Subscribed. this is the perfect example of explaining to a 5 year old kid.
This is super helpful! I love the simplicity of this explanation. Subscribed!
f of x is in big O of g of x if and only if there exists a k and an x-naught, such that for all x greater than or equal to x-naught, f of x is less than to k times g of x
you are the deep of man!!! thank you dude!
Incredible quality
Give lecture on - Brute Force, Greedy method, branch and bound, backtracking , dynamic programming , asymptotic analysis (best,worst,average cases), of time and space , upper and lower bound, basic concept of complexity classes- P, NP,Np-hard,NP-complete, graph and tree algorithm , depth breadth first traversal , tractable and interactable problem
How do you create your animations?
This is so amazing and easy to understand! Thanks a lot!
This is so brilliant! Keep doing such videos plz
Excellent video, thanks for making it available to us.
this is the best vedio i seen more than 10 vedios on big oh but this vedio made me understand sooo fast thanks a lot bro
Animations are just wonderfull. I-I c-can't hold back from hitting like button !
Nice video! Just as a small note: the code at 7:55 doesn't actually compute (approximate, really) the square root of a number, but the INVERSE of the square root. It's equivalent readable code would be: 1 / Math.sqrt(n). For anyone interested in the algorithm and the code check the Wikipedia page: en.wikipedia.org/wiki/Fast_inverse_square_root
Here are some slides that explain quite well how it works and how anyone could come up with it: www.bullshitmath.lol/FastRoot.slides.html#/
goddamn it, could you have a legend that shows what each math notation means? thanks lol
WOW, That's pretty clear!! Thanks.
what a wonderful and clear explanation. thank you
I found this explanation great, would help me alot if I saw it when I first learned about O notation :)
excellent explanation
I really love the content and the way you share it
Awesome video, loved the metaphors!
I just pause in the middle of the video and check the comment, move to another video.
same bruh
0:27 Biggest ''fuck you'' I've had all day.
Cool stuff
undefined behavior gives me unexpected great video.
1:16 this is kind of confusing. Your explanation of being 'fast' might make people think that it means that the algorithm is of a higher degree or complexity (like n is higher than log(n)), when in reality it's easier to imagine that Usian Bolt is O(1).
you rock man
Very well explained
excellent video!
This was a an awesome video!
brilliant
can anyone bother to explain what the code in 07:57 is?
czcams.com/video/p8u_k2LIZyo/video.html
It wasn't easy... I went throw 6 other videos so now your video made a sense to me.... But for anyone new it isn't easy... I recommend to watch this video at last after you have watched few others... It will make the concept smooth
Great! Thnx
great video
yo, this was really cool
not gonna lie, came for the thumbnail
I almost died when he say easy
I wasn't getting it until I saw Mario. I love Mario
thank you very very much from thai.
omg thank you
At this point I only work for exams without understanding jack sh1t
How do you not have more subscribers?
Bogosort #1!
genius!
It was starting to click with the umbrella but then I got lost again. I apologize master, I am a slow learner #anakinskywalker
subscribed for guilty spark
0:38
"easy, right ?" sike
that's the joke..
I'm one of the tomatoes!
This is the only video on Big-O I could find that uses the word "asymptotic" to define it. And yet it seems like you don't understand what it means. Because the conclusion should be that Big-O is completely useless, as all it tells us is what happens in a neighborhood of infinity, and nobody cares about that in practice.
Any other Whovians Jumped when they saw the TARDIS?
i came here for pokemeon
at 0:18 how many of you thought of church from RvB instead of halo? lol czcams.com/video/Rmc661a9IRY/video.html
n!
You heard it here first!
I clicked on this because the Pokemon
this video is confusing... lolol
Very Informative...........
czcams.com/channels/oscfxTBY93lYauulG-fBRw.html
www.mukeshrajput102.com/
not a very intuitive, introductory explanation. please go about it slower and more basic!!!!!!
Gg
I don't understand this one at all.
Obviously Scyther with Double Team is faster than mr. Bolt.
pokemon analogy? what's your audience? kindergarten?
why not kindergarden kids start learning these.