Algorithms: Big O Notation Example 1

[@hayden3774]

My left ear truly enjoyed this thorough explanation

[@ThePrlara2000]

I learned more in 10 minutes, than my 3 hour lecture yesterday!!! Thanks

[@discretemathvideos204]

Thanks! Glad it was helpful

[@Sazza-ll3qd]

been stuck on this for 4 days now and you just cleared up my problem, your a life saver!

[@discretemathvideos204]

Thanks for the feedback and glad it helped!

[@andyjohnson6520]

So glad I learn more from youtube than a class I'm paying $1200 for.....thanks for the video, this helped tremendously!

[@rainbow6siege345]

Same and learning online is shit too

[@gabrielmoreira1491]

THANK U SO MUCH! You don't know how much you have made me happy when I finally understood it. Best explanation I've heard, very detailed and very easy to understand. This is something that seems and that people tell us is harder than it is!

[@pandadog423]

5 years later this is still a great explanation, I always understood the basics of it but when it came to proofs I always got stumpted on how to prove it. thanks alot

[@p.c2750]

One min into your tutorial, i give you thumbs up because of paying attention to details

[@Hanzla_Rana]

my left ear liked the video

[@RicardoFloresRicardo]

My right ear understood all of this. Thank u

[@nveemusic]

10 mins of this literally increased my study efficiency

[@Ultrafresh987]

Thank you very much. I didn't listen during the 1hr lecture and I've got it all here in 10 mins. Thanks again

[@topDragon-f9t]

This mans in god sent! My prof just gave us notes and expected us to undertand. Been looking around everywhere for an explantion on Big O but you my friend had cleared all my doubts in under 10 mins! Thanks!

[@mk17173n]

i learned more from this video in 5 minutes than other videos that were hours long.

[@alikhalidsalim4865]

Your videos are the best videos on discrete math, on KZbin. What a legend !!!!! Please continue posting as many videos on Computer Science as you can! THANKSSSSSSS

[@quotablecode]

Been struggling with this notation till I stumbled upon this video. Thanks !

[@davidr3569]

Thank you for this! Best explanation that goes step by step AND gives reasoning for each step. Choosing k = 1 makes this a whole lot easier to process and makes this very repeatable for variations of this type of problem. Gave a like!

[@MrRANDUM145]

This helped a lot! I can actually understand what you are saying unlike my thick accented teacher

[@johncanzoneri8297]

Thank you!!! This video helped what my professor couldn’t do in hours of lecture

[@nathanielislas9245]

You explain things so well! Keep up the good work!

[@mrshodz]

great explanation. the simplicity of the explanation is wonderful.

[@vinayakanil4288]

You're a lifesaver dude, keep up the good work!!

[@kaho5004]

Makes so much more sense than my lectures. Thank you

[@WebSurfingIsMyPastime]

I'm 30 seconds in and I allready know this video is going to help explain alot of misunderstandings I've had trying to grasp big-O notation.

[@mk17173n]

do you know why he labeled x =5 as k?

[@GRAZIoficial]

Thank you from Brazil. It help me a lot!

[@potatoitis3326]

YOU ARE THE BEST! thank you so much!!!!! I was struggling with this for my test and you cleared up a lot of confusion.

[@WebSurfingIsMyPastime]

No updates in 2 years? Pls release more videos, and charge if you must, but bring them out, students such as myself will gladly pay for real working examples of these hard to grasp concepts! Thanks

[@Drewbydrew]

Fantastic! Thanks, that made way more sense than my professor's explanation did :)

[@headyshotta5777]

Great video. Only thing is that I had to watch it twice, switching earbuds halfway through so both my ears could hear.

[@juliannafotheringham7101]

sooooooo incredibly helpful! Thank you, angel!

[@sankalparora9261]

Amazing video! Clear, concise, to the point! Thanks!

[@themanwhoiscompeng1422]

your video's so helpful for cs students thanks a lot

[@StephenSumilang]

my left ear really enjoys this

[@thebarnold7234]

My left ear loved this

[@nurmukhambetserikbayev]

Oh my GOD I love you. Thank you Sir!. Hope u r doing well

[@Flutoid]

why don't more instructors highlight the fact that you don't need to have a specfic one solution for prooving big O. this has been confusing me for few weeks until now. Thank you so much.

[@KC-dg9pu]

im following with k=1 but the book i have then uses k=2 as an example and im completley lost. the example was is x^2 + 2x + 1 O(x^2). So for k=1, the solution was 4x^2 which i can get using your method. but for k=2, the solution was 3x^2 and i can't figure that part out.

[@snowdawner250]

Thank you! It was very clear and helpful!

[@Ali124hdkflc]

Very clear explanation. Thank you.

[@misterlight5115]

hmm the book were using in my college class just says to use 2 rules remove all the constants (5 +n becomes O(n)) and use only the highest order (so like x + x^2 becomes O(x^2)). However, this is a programming course so that could be why but this video still did help

[@krissharma7333]

Very Well Explained. Thank You Very Much.

[@discretemathvideos204]

You're welcome! Thanks for the positive feedback.

[@zayedalmazroui7942]

Great video! Is it necessary to use the second approach? Would it be sufficient to only use the first approach when proving?

[@junlee9437]

It helps a lot a lot.... Thank you!

[@goku_sama5348]

so the whole strategy to prove this, is to turn every term to the highest degree in the polynom, while x > 1 and then look for c and k. After that you are done with the prove, right?

[@vrius3335]

Wow great video.

[@dariennesee5928]

Thank you so much! I actually understand the concept now :)

[@jlee900]

Your videos are great! one question though, why can't x be equal or greater than 1 at around the 8:00 minute mark? Thank you and sorry for the very late comment

[@strawberryyogurt0]

@5:13 -- The lecturer should really have kept things consistent, especially for a beginner like myself. There really is no reason "when x >5" should have been specified when " x = 5 " was initially used. @5:24 - This is the point when you should have used " when x >5" because it is at this exact point when we're going to be experimenting with different values for "x" so the viewer/student can see what happens when we change the value of "x" --- The "What if" scenarios. My other suggestion would to have been to actually plug ever growing larger values into x and calculate the final values for those who are visual learners. x = 6, x = 10, x = 200, x = 2500, x = 100000000, etc which is "when x>5" finally makes conceptual sense. "When x>5" doesn't make sense in the "equation" written @5:13.

[@discretemathvideos204]

I appreciate the feedback. I tried to make it clear that this first example was done by exploration to illustrate the concept. The basic idea is that once x > k we need the inequality to hold. For this particular example, it was easy for me to find a value for k that gave us a nice C to make both sides equal. Once we get beyond this point where they are equal, the inequality holds. I stated that the following examples use a much easier strategy. Sure, maybe I should have added more examples for the exploration, but I am trying to keep the length of the videos down and focus on the strategy to find the C and k in the following examples. It seems like you were able to do that exploration on your own which is great!

[@strawberryyogurt0]

@@discretemathvideos204 .... Appreciate the reply. Rest assure that it’s not limited to one youtube teaching channel. I’ve seen various youtubers doing the same regardless of subject matter. Often for beginners, tutorials having consistency makes a difference. Inconsistencies may cause confusion. Slow vs quick learners. Bart vs Lisa Simpsons of the world. Certain learners appreciate shorter videos, however, there are also a subset that prefer videos that are just a tad longer, with a couple more examples to truly hammer home concepts and the applications of those concept. Finding the right balance is certainly an art. I would rather see vids be a bit more thorough even if that adds one or two additional minutes - especially when they’re tutorials (as opposed to topic cliff notes). Specifically for ‘when x =5’ versus ‘when x > 5’, I decided to scroll through the comment section to see if someone may have offered clarification. Regardless, nice video. I got something out of it.

[@guliyevshahriyar]

Thank you very much teacher!

[@sonsc5283]

very good explanation!

[@goku_sama5348]

when 28x^2 is bigger than 3x^2 + 25 our O(x) = x^2, we can forget the 3 and the 25, since they are constants, right?

[@TheeWHATommy]

This is amazing, thank you!

[@madjidsmail5684]

I learned more in 10 minutes, than my 3 hour lecture

[@robertmunroe9635]

So my big thing is how can you justify a proof by simply bumping the right side up to be greater in value than it would be previously.

[@discretemathvideos204]

Sorry I hadn't seen these comments earlier! All you have to do is find a C and k for which the inequality holds. this technique does that in a quick and simple way. There is nothing incorrect in any of the statements.

[@MrxGamex69]

Thanks a bunch!

[@xuanhuang4071]

A little bit confused that why you plug in value for x directly? Shouldn't we need to do 3x^2+25

[@xuanhuang4071]

Nevermind, I figured it out. But, still confused about x= 5 is k.

[@discretemathvideos204]

Sorry I hadn't seen these comments earlier! This is just an exploration where it turns out that x = 5 gives us a nice C = 4 to make both sides equal. Then we can see that once x > 5, the inequality holds, so that makes the k = 5. After that, I show a much simpler way to do this. I tried to state that before this first example, but it seems some people missed that or got hung up on this example.

[@ΆριστοςΚαισης]

Great explanation!!

[@discretemathvideos204]

thanks! glad it helped.

[@fahinrahman8951]

so when you do the method of changing every variable to the highest degree, will k always be > 1 ( x > 1)?

[@raykos4257]

Are C and k assumed to be positive integers?

[@Ali-kl3ql]

We can take a lim both sides and C shows itself easily, without testing numbers.

[@ericcheek2983]

Awesome video, thank you so much

[@Smiteforce]

could you perhaps normalize the sound on this video? the volume is very low

[@JossinJax]

Why is k = 5 when you said x =5 and x has to be greater than k?

[@haneulkim4902]

have the same question, did u find the answer?

[@xogmaster]

@@haneulkim4902 seriously wtf, this one thing has me so confused! the definition says x must be greater than k, but he set k to 5 when x was 5! i don't get it!

[@yoowon-hye9270]

Ok lemme try to explain based on my knowledge. Let it be known that k is the "base case" of the possible values of input size n (the closest minimum value that satisfies the inequality). To perform what's on the left-hand side of the inequality (f(n)), we had to pick some value for n, which in this case is 5. We performed the left-hand expression and come up with the result of 100. Now we have to find a constant that would make the inequality true (i.e. to make 100

[@discretemathvideos204]

Sorry, I hadn't seen all of these comments earlier! The first example is just sort of done by exploration and it turned out that x = 5 gave us some nice numbers. The point is that once the functions become equal at x = 5, once we go beyond that (x > k, where k=5) we know the inequality will hold. I mention that later, there's a much simpler way to do this, but wanted to get the concept across first.

[@gracehu3031]

THANK YOU!: D

[@weebiezz]

Quite helpful

[@sahilghuge5302]

THANKYOU ❤️

[@giizemtiske]

Why did we say x = 5?

[@cansu5237]

Thank you

[@nihal1805]

Thanks ❤️😌

[@pegahfallah3770]

bless ur soul

[@noodleboi5053]

what u got against my right ear

[@ChiPyon]

Awesome thanks a lot

[@timewrath7723]

Why was 25 converted to an x^2 function at around 7:03?

[@discretemathvideos204]

the whole strategy here is to find a C value to make the inequality hold. The easiest way to do that is to bump every term up to the highest degree and simply combine like terms. Then the C is right therw!

[@lesliechiu1437]

Hi sir,Could you explain how to get x=5?

[@discretemathvideos204]

That first example is really just done by exploration to explain the concept. I happened to notice that x=5 gave us a nice value for C. But the following examples show a much simpler strategy, so don't get hung up on where the 5 came from. It was just a value I knew would work well because I created the problem.

[@sharifi101]

how to solve this kind of big-oh? show that (x^2-1)/(x-1) is o(x) tnx

[@discretemathvideos204]

Think about how that function you gave simplifies or use long division to simplify it.

[@abdulrahmanzidane2271]

You must come and give lectures instead of our prof :)

[@Bob-gi2gh]

Hold up is this Casually Explained's burner account?

[@shimulbhattacharjee5137]

Can I take x=3 ?

[@discretemathvideos204]

Sorry I hadn't seen these comments earlier! I'm not sure where you are referring to. But there is no unique k or C value, you just have to find a pair that works.

[@dragg0511]

thx man

[@jakobsymchych3846]

my left ear thanks you

[@kidcharlemagne9942]

THANK YOU!

[@discretemathvideos204]

You're welcome, glad it helped!

[@marcousosewelle5501]

3x^2 + 25/x2

[@miguelcastorena4293]

thanks for the explanation

[@AhmedTarek-ob1zt]

your sound is familiar , u sound like the guy from trevtutor

[@bubblesgrappling736]

but what is g(x) in relation to f(x)? I understand that f(x) i some arbitrary function, but it doesnt make sense to describe a function in relation to another function that we do not know either???

[@discretemathvideos204]

the idea is that you are given the function f(x) and trying to say it is on the order of g(x). g(x) becomes a simple upper bound on f(x)

[@dimakavetskyy2082]

YOOOOOOOOOOOOOOOOOOOOOO

[@sameertrimade9691]

horrible lecture

[@Walruz1000]

How do you decide that g(x) is going to be 5^2 in the example? I dont understand how you chose that value, could you explain it? I think it would help me understand this a lot better.

[@Walruz1000]

Is it because x^2 is the highest order in the function, and x = 5?

[@masoudshairzadeh6820]

I believe he picked 5 as a arbitrary number to make it easier to pick c and k