What Is Big O? (Comparing Algorithms)

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.org/wiki/Big_O_n...
Analysis of Algorithms: en.wikipedia.org/wiki/Analysi...
Time Complexity: en.wikipedia.org/wiki/Time_co...
Sorting: en.wikipedia.org/wiki/Sorting...
Fast Inverse Square Root: en.wikipedia.org/wiki/Fast_in...
Picture Credits:
s-media-cache-ak0.pinimg.com/...

[@ricardoamaya2500]

Searched for Big O, came for the pokemon

[@artbridder]

stayed for the pokemon?

[@DrRiq]

it's "came for big O, stayed for the Pokemon"

[@kingshukcs]

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!!

[@keymaster9306]

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.

[@Sparkesix]

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.

[@andrewdelgado9815]

Most straight forward video I have seen on Big O. Great job!

[@alonsorobots]

Love these videos! Would love to see more CS and Algorithms explains this way =)

[@pc8505]

This is so amazing and easy to understand! Thanks a lot!

[@alexanderf8451]

Props for including fast inverse square root!

[@kyle.nguyen]

This is a really great visualization of the Big O concept

[@jobsjaz369r7]

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 😊

[@williamw8590]

This is super helpful! I love the simplicity of this explanation. Subscribed!

[@neo_snakejazz]

Excellent video, thanks for making it available to us.

[@kerryjackson6773]

Awesome video, loved the metaphors!

[@CarlosAlbertBR]

what a wonderful and clear explanation. thank you

[@sajaal-dabet148]

This is so brilliant! Keep doing such videos plz

[@poggly]

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).

[@PrabhathDarshana]

WOW, That's pretty clear!! Thanks.

[@aidayana3253]

I really love the content and the way you share it

[@jamesmiller2521]

Algorithms! Gotta understand 'em all!

[@classcube]

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.

[@Jemmeh]

This is fantastic. Love the metaphors, it helps it be more tangible. Thanks for the video!

[@itsiwhatitsi]

This seems like a David Lynch film: hard to understand but many people like it anyway

[@khushiaswani6500]

it looks so professional but personally I didnt get a thing lol

[@flatbox1416]

0:38, I nearly had a stroke.

[@martintirpak1033]

I found this explanation great, would help me alot if I saw it when I first learned about O notation :)

[@almostbutnotentirelyunreas166]

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.

[@rayerdyne]

Animations are just wonderfull. I-I c-can't hold back from hitting like button !

[@karthiksantosh3475]

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

[@Revycake]

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!!

[@FindusGame11]

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

[@kneeboardcrasher]

This was a an awesome video!

[@second_second_]

Wow, the cutest video about Big-0 i've ever watched (pokemon). wished i understand other references as well

[@rebecaperez4472]

this is the best explanation of big O I have seen.

[@shepbryan4315]

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

[@LetsBeHuman]

very well explained with examples and graphics. Subscribed. this is the perfect example of explaining to a 5 year old kid.

[@kallihale5197]

This deserves more views.

[@karimk8551]

excellent explanation

[@maraud3r_]

Very well explained

[@tsunghan_yu]

excellent video!

[@gisforgirard]

this is literally the best video I have ever seen on the entire internet. thank you for this.

[@carloslaguna7036]

How do you create your animations?

[@bren007pie2]

Incredible quality

[@Malik-qh7wq]

Great! Thnx

[@simonthelen5910]

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.

[@zyrocks2]

still no freaking clue what "O" is.. is it just there as a decoration? no clue...

[@gemyellow]

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'.*

[@gingeral253]

Cool stuff

[@affshafee.rahman]

If at 6:44, the worst, average and best cases are all big-Ohs, then where does big-Theta and big-Omega fit?

[@user-yd9xy3rb4x]

you rock man

[@gkmishra2009]

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

[@LuvElaYay]

great video

[@MrKibujo]

undefined behavior gives me unexpected great video.

[@mattwaters9008]

comp sci and pokemon. finally the youtube algo doing something right

[@charlliemurphy8381]

brilliant

[@maulob1523]

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

[@madghostek3026]

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

[@srincrivel1]

yo, this was really cool

[@dimitrijep7872]

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))

[@matthewjackson9260]

I only liked your comment because you can send it bro.

[@jaganmathadevidasi5786]

Thank u ☺️

[@ikki2526]

thank you very very much from thai.

[@javierbg1995]

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#/

[@nguyenquangminh4814]

omg thank you

[@sudoku37]

I just pause in the middle of the video and check the comment, move to another video.

[@khushiaswani6500]

same bruh

[@vojtechfric9470]

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.

[@pingshiyu]

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.

[@rafaelmarques1773]

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.

[@jamebonez]

I was having a hard time understanding the topic until I watched this video. The examples were very helpful.

[@marklu5521]

goddamn it, could you have a legend that shows what each math notation means? thanks lol

[@grainfrizz]

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

[@omerkaraca2939]

you are the deep of man!!! thank you dude!

[@aresxena6632]

0:27 Biggest ''fuck you'' I've had all day.

[@imadhamaidi]

can anyone bother to explain what the code in 07:57 is?

[@oolivergraham]

kzbin.info/www/bejne/pmnYkJ5oga6Nr9E

[@abeer141]

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

[@muhammadneanaa1611]

genius!

[@robotspgc]

How do you not have more subscribers?

[@janmichaelbesinga3867]

I almost died when he say easy

[@puglife1343]

not gonna lie, came for the thumbnail

[@TimeLordVictorious11]

at 0:18 how many of you thought of church from RvB instead of halo? lol kzbin.info/www/bejne/iJ7GZ2lnlp58iLs

[@Idan-tc5rt]

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).

[@opus_X]

Bogosort #1!

[@manifest_it_man]

subscribed for guilty spark

[@adamblackler488]

n! You heard it here first!

[@knightonhd1144]

It was starting to click with the umbrella but then I got lost again. I apologize master, I am a slow learner #anakinskywalker

[@InstaCody]

I wasn't getting it until I saw Mario. I love Mario

[@dotwarner17]

I'm one of the tomatoes!

[@licolhavaiia2205]

0:38 "easy, right ?" sike

[@DrRiq]

that's the joke..

[@meghanabhange13]

Any other Whovians Jumped when they saw the TARDIS?

[@Onnethox]

At this point I only work for exams without understanding jack sh1t

[@Annettewalker-nq2jf]

i came here for pokemeon

[@killerwhiteshark1797]

I clicked on this because the Pokemon

[@EUROSPORTS4TECH]

Gg

[@salek991]

Obviously Scyther with Double Team is faster than mr. Bolt.

[@dailytimelapse8414]

this video is confusing... lolol

[@MukeshRajput1982]

Very Informative........... kzbin.info/door/oscfxTBY93lYauulG-fBRw www.mukeshrajput102.com/

[@BruceRicard]

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.

[@gazorb2]

I don't understand this one at all.

[@webgpu]

pokemon analogy? what's your audience? kindergarten?

[@LetsBeHuman]

why not kindergarden kids start learning these.

[@DanT-iu6oc]

not a very intuitive, introductory explanation. please go about it slower and more basic!!!!!!