What Is Big O Notation?
In this video, we take a look at Big O notation. We go through how Big O notation came about and why it's so useful as a method of measuring efficiency of algorithms. We then go through some examples of you can find the Big O runtime of various algorithms.
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music:
October by Kai Engel freemusicarchive.org/music/Ka...
November by Kai Engel
freemusicarchive.org/music/Ka...
Cobweb Morning by Kai Engel
freemusicarchive.org/music/Ka...
Пікірлер: 354
i love how 3blue1brown has created a new genre
@vgarzareyna
3 жыл бұрын
I’ve seen a lot of videos similar to 3b1b’s lately and I love them
@evanward5045
3 жыл бұрын
You commented exactly what I and many others were going to comment
@S1lentG4mer
3 жыл бұрын
I thought this was 3b1b
@chrisvinciguerra4128
3 жыл бұрын
Well he did make the Python library that this video used for its graphics so yeah that’s a reason why it’s similar
@markgross9582
3 жыл бұрын
Yeah. The animation styles seem similar too, so they may be using his library
Soo good. You broke down a commonly misunderstood topic in an intuitive and engaging way. I love it!
@Reducible
4 жыл бұрын
Thanks Tiffany! I appreciate it!
A 3Blue1Brown for computer science. Awesome. This might end up being my favourite channel.
I cant understand how youtube isn't recommending these videos. So elegantly explained, and the animations, OMG!
@sifsif2725
3 жыл бұрын
It just recommended this to me xD
@astphaire
3 жыл бұрын
I mean his enunciation isn’t great
@Warpadable
2 жыл бұрын
Well every people watching this had this recommended... You included. Otherwise how did you find it? I agree it is awesome though.
Wow, I actually think 3B1B has created a revolution in how we should think of structuring educational videos. I'm willing to bet that in the near future his visualization program and video structure are going to be used by MANY more people and hopefully even inspire some teachers to use his methods in class. Amazing work @Reducible! You should think about doing an "Essence of Computer Science" in the future!
Easily some of the best computer science videos on youtube and definitely better than my CS professors :). Thank you for putting in all this work!
I came to this video with high hopes as you used Manim, yet, I was blown away with how detailed and thorough you were. I paused the video so many times, yet, not only was told what I was thinking, I was told it was normal, to think and ponder on it. I am actually blown away on how you able to teach something so simple that is a basic need for computer scientises in a way that makes me wonder how tf didn't I think of that!
this is the on video that finally settled my confusion with asymptotic notations. THANK YOU SO. MUCH. THIS IS INSANELY GOOD AND HIGH-QUALITY!!
Definitely not forgetting Big O notation for a really long time! Excellent video sir! Thanks
I've seen many channels using manim. Beside its creator, this is the most original and really good one. I'm trying to have my own channel where a explain my area with other students, and I'm having trouble programing the animations, so I need to say thanks for this beautiful work of yours.
A professor once asked the big O of an algorithm, to which I replied "O(n!^(n!))." He had to admit that I was right, then he rephrased the question as "what is the smallest big-O of the algorithm?" Never forget that a big-O is not necessarily the best bound on an algorithm, just one of many bounds
@12-343
2 жыл бұрын
If the answer to the question is really O(n!^n!), I think whoever wrote it is having a very rough time
@Magnogen
2 жыл бұрын
@@12-343 it's probably my code tbh
@wolfranck7038
2 жыл бұрын
If I'm not mistaken, the "smallest big O" is called big theta !
@klobiforpresident2254
2 жыл бұрын
@@wolfranck7038 Not quite. There are O and Omega. Big O is *an* upper bound. Often we mean the smallest (known) upper bound. Similarly Ω is *a* lower bound. Often we mean the largest (known) lower bound. When O and Ω are identical then that is called Θ.
@wolfranck7038
2 жыл бұрын
@@klobiforpresident2254 yeah but if you think about it, the "smallest" big O will be of the same order as the function concerned, thus also being big omega, and it will be in big theta Because smaller than that would be only big omega and bigger thant that would only be big O (It's clearly not a rigorous explanation but can't do much better in a YT comment)
Best explanation of Big O I have come across!
the best video about O notation, you bring all together, even lim, cool
Thanks these are lifesavers for my current course.
I love your videos for accuracy and clear content. Please upload videos on different algorithms and shortest paths.
This is hands down the best explanation of big O notation!!! Instantly subscribed to your channel. 👌👌👌😘😘 BTW your voice is just like 3blue 1brown!
Hope your channel keeps growing!
Never was into computer science, but it feels good to finally understand what the notation actually mean after encountering it in my higher-end math classes from time to time. Thank you!
Thanks for the time you put into this video, being able to reduce complex things to something I could explain to a highschool student is thrilling in a nerdy way
Beautiful presentation accompanied with fantastic music of enlightenment!
Amazing video! Love the use of manim.
thanks for your efforts , I just discovered your channel and it's INCREDIBLY helpful !
What a great video! Thanks so much!
This is the best explanation I've ever seen.
A very simple and detailed explanation. Thank you very much
This is so easy to understand....roughly 2 years ago I tried to gather this information on Computational complexity from a big book and ended up understanding very little.
These are so wonderful - thank you !
Thank you for this amazing video!
Really instructive, as always Keep up the amazing work ;)
you have the best explanation. thanks for the video
by far it is the best explanation after years of search.
Well presented! Thank you.
Thanks so much! You have invaluable content!
Such a great video thank you so much I honestly don’t have enough words to thank you appreciate that
BEST VIDIEO ON BIG O NOTATION!!! every other video out there just leaves me more confused. thank you.
This masterpiece omg thank you so much!
Wow, this was incredibly good. Thank you.
@ 14:55 "we can actually use this 'symme-tree' to help us"
I loved this video. Thank you !
Great work, thanks!
This video helped me alot. Thank you:)
Love how to find big o with graph explanations.. thank you 😀😀
Thank you so much and I really appreciate the video.
Great video!! I’ve always have doubts about this topic.
How come I noticed this masterpiece so late!? Definitely subscribing!
Good video, keep up the good work!!
You are amazing, please upload more videos.
Very well explained! I guess I will quote this video in my next complexity discussion at work :-D
Clearest, most complete Big-O video I've seen. Kudos. It looks like you used Grant's manim package to create this. I have been thinking of learning manim so I can create a video giving some insight into why the radix sort is so fast. Work doesn't leave me much time for such pleasures, though; you do such a good job with this, if you are interested I can privately explain the insight so you could make the video if it appeals to you.
Thanks! I finally undestood it!
This was amaaaazing
Was expecting several animations about other big O examples, like exponential one. It is very interesting to see them in comparison.
Great video keep up the good work
Nicely explained...
just put some thinking pi's and this literally becomes 3blue 1brown video!!! Really great channel
@playerscience
3 жыл бұрын
Exactly! He is the 3blue 1brown of Computer science. 😎🔥🔥🔥
ABSOLUTELY AWESOME I-
as a junior in cs right now, in my opinion, this is a must watch for all people trying to get a degree in programming
Maaaaan this is amazing ♥️♥️♥️
So good!
u explained it sooooo goooood, thanks
incridible! just continue bro
who came from 3blue1brown’s post?
@brooksbryant2478
3 жыл бұрын
Me
@LeoStaley
3 жыл бұрын
Which one?
@bazsnell3178
3 жыл бұрын
Me
I remember this topic being explained in algorithm courses very similarly.
O(2^N) : "Yo, I'm so complex" O(N!) : "What was that, punk?"
Now I want big O of big O notation, to group like growth rates together : polynomials, exponentials, and so on.
I love this channel
Cool video.
It would be an understatement to say this channel is underrated
大學的演算法 當初根本聽不懂 這個影片超有幫助 感謝講解
Great video i love the topics and the way that have been presented may teacher have not your skills, please more videos on running algorithmes programming ideas, thank you, i have subscribed to tthe channel.
Jeez I learned more here in 15 mins than a few weeks of my statistics and numerical methods class...
This is so great
i didnt come from 3b1b but im suprised at quality of these videos
I noticed a small error in your video. You typed two quotation marks in LaTeX at 9:59 . They are both ending quotation marks. The way to fix this is to use this markup: ``this will be surrounded with proper quotation marks when rendered in \LaTeX’’ Notice that I used two single quotes at the end (‘’) not a double quote (“).
@johnmeyers8542
2 жыл бұрын
Good catch. Although you missed 'defintiion' spelled with the lesser used two 'i's. Neither latex or other rubberised products will help with that one.
I want to give you a hug bro!
Hey good video explaining it. I think including the Factorial class would have been useful. While yes you dont see those outside graphs often, making an algoritmh on your own and recognizing to stay away from that class is practical
you probably should've added O(sqrt n) and O(n!) to your "common running times" list since they do appear quite often as well
Man manim is awesome
O(?) is deep and important in understanding processes in general, not just computing. Social structures scale in scary ways. Some stuff works great at dining room table scale (N~6), is still functional at the scale of a monastery (N ~ 100) but when they scale to small countries ( N ~ 20MM) let alone large countries ( N ~ 300 MM ) or huge countries ( N ~ 1 Billion) it hits the fan. Central planning for example. The Soviets set up an office to make sure everything was fairly priced relative to other stuff. Easy right? But there were N ~ 25 MM items in the economy. So relative fairness is N^2, but everything is fair compared to itself, so N^2 - N. Further comparison is sort of symmetric, so (N^2 -N)/2. Big improvement but when N = 25 MM, O(fair) ~ 312 trillion. Poor aparatchicks. (Tom Sowell cited this case) { if a is fair relative to b and b is fair relative to c, is a fair relative to c? How much would this improve things?}
@jursamaj
Жыл бұрын
That argument is obviously fallacious. You don't need to compare the price of every type of watch to every type of car, and every type of bread, etc. The watches only need compared amongst themselves, and to some baseline.
Awesome.
I keep reading the text in 3blue1brown's voice
@joeyhardin5903
3 жыл бұрын
ikr!!
The Man.The Myth.The Teacher
The second definition is quite understandable
Glad my teachers taught me well lol.
The best !!!
Oh I thought this was 3blue1brown but with an odd accent. Great video, might I recommend making your visual style a tiny bit more distinct. Since honestly its great to have a thing that makes your channel stand out a bit. Like I think you even picked the same font, unless Im mistaken
11:45 It's not really true that there should be such a limit. It may not exist. For example g(n) / f(n) may by 1 for even n's and 2 for odd n's. So there's no limit in this case. Even more. It's true that for f(n) = n and g(n) = n^2 it's true that n = O(n^2). But g(n) / f(n) = n has no limit.
@diegocfq
3 жыл бұрын
Yeah, it's supposed to be lim sup instead of just lim and an absolute value operator should be applied on the numerator of that fraction.
@DavidPysnik
3 жыл бұрын
How would lim sup help Сергей Обритаев's example? if f(n) = n and g(n) = n^2, the limit as n goes to infinity of g(n)/f(n) would not exist because it goes to infinity, so the lim sup of this expression going to infinity would also not exist. Even with lim sup in that definition shown at 11:45, it doesn't allow n = O(n^2) as the original definition does, so Сергей Обритаев's criticism does not seem fixed.
@johnmcleodvii
2 жыл бұрын
O notation does not require that the function has a strict limit in the terms that calculus does. If odd numbers for input are one growth in n and even numbers are something other growth in n, the O notation would be for the faster growing one. So in the example where odd numbers had linear growth and even numbers had n² growth, the O notation would be O(n²). Off the top of my head, I can think of no algorithms that have significantly different behaviors for even and odd n.
If only I saw this before my discrete mathematics exam
That last example emphasises the importance of caching - caching would reduce the runtime to O(n) worst-case and O(1) best-case (of course, it could also be reduced to O(n) simply by multiplying the recursive result by 2)
It's showtime!
Ur awsumm 🙏
I am here to cry over my upcoming tests🙂
Thanks
That is a nice video one. Please bring a video on "Space Complexity of an algorithm". Thank you.
At 15:53 table 1->1, 2->2, 3->4, 4->8, 5->16; at 16:15 If n=k, Count = 2^(k-1)= 2^k/2
I bring up BigO at work and people's eyes glaze over. I've stopped trying to explain, but damn with this video I think anyone could understand it!
Do someone know how this guy makes its animations? I would like to learn to make my classes more visual
What is difficult with this Definition? We do not define O(f) but we define =O(f) the Equal Sign has now no longer the meaning "equal". Example if f = O(g) and h = O(g) then f and h may not equal. if the = has the meaning "equal" O(f) have to be a function, but this is not the case.
@perrydimes6915
2 жыл бұрын
You're right, it is better to think about it as set inclusion. If you know anything about set theory, this is the "is in" or "is an element of" or simply ∈. So we would say f ∈ O(g), and h ∈ O(g). I believe this is the single biggest issue with understanding, because we're using an equals sign for something that is NOT equality. O(g) is a set. f, g, and h are all functions.
12:20 I argue that you can cram extra items between constant and logarithmic, by considering the inverse of the Ackermann function. n=3 would equal the cube root of 3. n=2 would be 1 (2/2) and n=1 would be 0 (1-1)
Well done! What tool(s) are you using to create this content?
@askii2004
3 жыл бұрын
It's liked in the description! It utilizes manim, which was developed by Grant Sanderson (3Blue1Brown).