Algorithms: Big O Notation Example 1

  Рет қаралды 207,401

Discrete Math videos

Discrete Math videos

6 жыл бұрын

Пікірлер: 113
@hayden3774
@hayden3774 Жыл бұрын
My left ear truly enjoyed this thorough explanation
@ThePrlara2000
@ThePrlara2000 6 жыл бұрын
I learned more in 10 minutes, than my 3 hour lecture yesterday!!! Thanks
@discretemathvideos204
@discretemathvideos204 6 жыл бұрын
Thanks! Glad it was helpful
@Hanzla_Rana
@Hanzla_Rana Жыл бұрын
my left ear liked the video
@Sazza-ll3qd
@Sazza-ll3qd 6 жыл бұрын
been stuck on this for 4 days now and you just cleared up my problem, your a life saver!
@discretemathvideos204
@discretemathvideos204 6 жыл бұрын
Thanks for the feedback and glad it helped!
@pandadog8343
@pandadog8343 Жыл бұрын
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
@HehLul
@HehLul Жыл бұрын
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!
@alikhalidsalim4865
@alikhalidsalim4865 4 жыл бұрын
Your videos are the best videos on discrete math, on KZfaq. What a legend !!!!! Please continue posting as many videos on Computer Science as you can! THANKSSSSSSS
@davidr3569
@davidr3569 2 жыл бұрын
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!
@sankalparora9261
@sankalparora9261 3 жыл бұрын
Amazing video! Clear, concise, to the point! Thanks!
@mk17173n
@mk17173n 4 жыл бұрын
i learned more from this video in 5 minutes than other videos that were hours long.
@nathanielislas9245
@nathanielislas9245 3 жыл бұрын
You explain things so well! Keep up the good work!
@johncanzoneri8297
@johncanzoneri8297 5 жыл бұрын
Thank you!!! This video helped what my professor couldn’t do in hours of lecture
@Ultrafresh987
@Ultrafresh987 2 жыл бұрын
Thank you very much. I didn't listen during the 1hr lecture and I've got it all here in 10 mins. Thanks again
@p.c2750
@p.c2750 3 жыл бұрын
One min into your tutorial, i give you thumbs up because of paying attention to details
@vinayakanil4288
@vinayakanil4288 4 жыл бұрын
You're a lifesaver dude, keep up the good work!!
@potatoitis3326
@potatoitis3326 2 жыл бұрын
YOU ARE THE BEST! thank you so much!!!!! I was struggling with this for my test and you cleared up a lot of confusion.
@Drewbydrew
@Drewbydrew 5 жыл бұрын
Fantastic! Thanks, that made way more sense than my professor's explanation did :)
@quotablecode
@quotablecode 3 ай бұрын
Been struggling with this notation till I stumbled upon this video. Thanks !
@mrshodz
@mrshodz Жыл бұрын
great explanation. the simplicity of the explanation is wonderful.
@GRAZIoficial
@GRAZIoficial 3 жыл бұрын
Thank you from Brazil. It help me a lot!
@fernandogmail1
@fernandogmail1 3 жыл бұрын
thank you, discrete math lord
@juliannafotheringham7101
@juliannafotheringham7101 2 жыл бұрын
sooooooo incredibly helpful! Thank you, angel!
@RicardoFloresRicardo
@RicardoFloresRicardo Жыл бұрын
My right ear understood all of this. Thank u
@nveemusic
@nveemusic 5 жыл бұрын
10 mins of this literally increased my study efficiency
@decayedjollyrancher88
@decayedjollyrancher88 7 ай бұрын
😀
@andyjohnson6520
@andyjohnson6520 3 жыл бұрын
So glad I learn more from youtube than a class I'm paying $1200 for.....thanks for the video, this helped tremendously!
@rainbow6siege345
@rainbow6siege345 3 жыл бұрын
Same and learning online is shit too
@kaho5004
@kaho5004 Жыл бұрын
Makes so much more sense than my lectures. Thank you
@snowdawner250
@snowdawner250 4 жыл бұрын
Thank you! It was very clear and helpful!
@dariennesee5928
@dariennesee5928 2 жыл бұрын
Thank you so much! I actually understand the concept now :)
@themanwhoiscompeng1422
@themanwhoiscompeng1422 4 жыл бұрын
your video's so helpful for cs students thanks a lot
@user-hx9ds3mx7i
@user-hx9ds3mx7i Жыл бұрын
my left ear really enjoys this
@Faylasuf57
@Faylasuf57 3 жыл бұрын
Very clear explanation. Thank you.
@zayedalmazroui7942
@zayedalmazroui7942 3 жыл бұрын
Great video! Is it necessary to use the second approach? Would it be sufficient to only use the first approach when proving?
@headyshotta5777
@headyshotta5777 Жыл бұрын
Great video. Only thing is that I had to watch it twice, switching earbuds halfway through so both my ears could hear.
@WebSurfingIsMyPastime
@WebSurfingIsMyPastime 4 жыл бұрын
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
@junlee9437
@junlee9437 4 жыл бұрын
It helps a lot a lot.... Thank you!
@TheeWHATommy
@TheeWHATommy 3 жыл бұрын
This is amazing, thank you!
@MrRANDUM145
@MrRANDUM145 3 жыл бұрын
This helped a lot! I can actually understand what you are saying unlike my thick accented teacher
@ericcheek2983
@ericcheek2983 5 жыл бұрын
Awesome video, thank you so much
@WebSurfingIsMyPastime
@WebSurfingIsMyPastime 4 жыл бұрын
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
@mk17173n 4 жыл бұрын
do you know why he labeled x =5 as k?
@thebarnold7234
@thebarnold7234 Жыл бұрын
My left ear loved this
@krissharma7333
@krissharma7333 6 жыл бұрын
Very Well Explained. Thank You Very Much.
@discretemathvideos204
@discretemathvideos204 6 жыл бұрын
You're welcome! Thanks for the positive feedback.
@nurmukhambetserikbayev
@nurmukhambetserikbayev 6 ай бұрын
Oh my GOD I love you. Thank you Sir!. Hope u r doing well
@vrius3335
@vrius3335 4 жыл бұрын
Wow great video.
@jlee900
@jlee900 7 ай бұрын
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
@sonsc5283
@sonsc5283 3 жыл бұрын
very good explanation!
@misterlight5115
@misterlight5115 3 жыл бұрын
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
@madjidsmail5684
@madjidsmail5684 3 жыл бұрын
I learned more in 10 minutes, than my 3 hour lecture
@MrxGamex69
@MrxGamex69 6 ай бұрын
Thanks a bunch!
@fahinrahman8951
@fahinrahman8951 3 жыл бұрын
so when you do the method of changing every variable to the highest degree, will k always be > 1 ( x > 1)?
@guliyevshahriyar
@guliyevshahriyar Жыл бұрын
Thank you very much teacher!
@pegahfallah3770
@pegahfallah3770 5 жыл бұрын
bless ur soul
@ChiPyon
@ChiPyon 5 жыл бұрын
Awesome thanks a lot
@user-uk6gj7up6i
@user-uk6gj7up6i 6 жыл бұрын
Great explanation!!
@discretemathvideos204
@discretemathvideos204 6 жыл бұрын
thanks! glad it helped.
@gracehu3031
@gracehu3031 2 жыл бұрын
THANK YOU!: D
@Flutoid
@Flutoid 3 ай бұрын
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.
@raykos4257
@raykos4257 7 ай бұрын
Are C and k assumed to be positive integers?
@goku_sama5348
@goku_sama5348 9 ай бұрын
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?
@sahilghuge5302
@sahilghuge5302 4 ай бұрын
THANKYOU ❤️
@weebiezz
@weebiezz 3 жыл бұрын
Quite helpful
@kidcharlemagne9942
@kidcharlemagne9942 6 жыл бұрын
THANK YOU!
@discretemathvideos204
@discretemathvideos204 6 жыл бұрын
You're welcome, glad it helped!
@goku_sama5348
@goku_sama5348 9 ай бұрын
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?
@KC-dg9pu
@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.
@divy2783
@divy2783 3 ай бұрын
thx man
@cansu5237
@cansu5237 2 жыл бұрын
Thank you
@nihal1805
@nihal1805 3 жыл бұрын
Thanks ❤️😌
@glazfe8112
@glazfe8112 4 жыл бұрын
could you perhaps normalize the sound on this video? the volume is very low
@xuanhuang4071
@xuanhuang4071 5 жыл бұрын
A little bit confused that why you plug in value for x directly? Shouldn't we need to do 3x^2+25
@xuanhuang4071
@xuanhuang4071 5 жыл бұрын
Nevermind, I figured it out. But, still confused about x= 5 is k.
@discretemathvideos204
@discretemathvideos204 4 жыл бұрын
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.
@Bob-gi2gh
@Bob-gi2gh 3 жыл бұрын
Hold up is this Casually Explained's burner account?
@jakobsymchych3846
@jakobsymchych3846 Жыл бұрын
my left ear thanks you
@Walruz1000
@Walruz1000 3 жыл бұрын
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
@Walruz1000 3 жыл бұрын
Is it because x^2 is the highest order in the function, and x = 5?
@masoudshairzadeh6820
@masoudshairzadeh6820 10 ай бұрын
I believe he picked 5 as a arbitrary number to make it easier to pick c and k
@JossinJax
@JossinJax 5 жыл бұрын
Why is k = 5 when you said x =5 and x has to be greater than k?
@haneulkim4902
@haneulkim4902 4 жыл бұрын
have the same question, did u find the answer?
@xogmaster
@xogmaster 4 жыл бұрын
@@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
@yoowon-hye9270 4 жыл бұрын
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
@discretemathvideos204 4 жыл бұрын
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.
@Ali-kl3ql
@Ali-kl3ql 3 жыл бұрын
We can take a lim both sides and C shows itself easily, without testing numbers.
@timewrath7723
@timewrath7723 4 жыл бұрын
Why was 25 converted to an x^2 function at around 7:03?
@discretemathvideos204
@discretemathvideos204 4 жыл бұрын
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!
@giizemtiske
@giizemtiske 4 ай бұрын
Why did we say x = 5?
@strawberryyogurt0
@strawberryyogurt0 4 жыл бұрын
@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
@discretemathvideos204 4 жыл бұрын
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
@strawberryyogurt0 4 жыл бұрын
@@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.
@noodleboi5053
@noodleboi5053 Жыл бұрын
what u got against my right ear
@robertmunroe9635
@robertmunroe9635 5 жыл бұрын
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
@discretemathvideos204 4 жыл бұрын
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.
@abdulrahmanzidane2271
@abdulrahmanzidane2271 3 жыл бұрын
You must come and give lectures instead of our prof :)
@sharifi101
@sharifi101 6 жыл бұрын
how to solve this kind of big-oh? show that (x^2-1)/(x-1) is o(x) tnx
@discretemathvideos204
@discretemathvideos204 6 жыл бұрын
Think about how that function you gave simplifies or use long division to simplify it.
@AhmedTarek-ob1zt
@AhmedTarek-ob1zt 3 жыл бұрын
your sound is familiar , u sound like the guy from trevtutor
@lesliechiu1437
@lesliechiu1437 4 жыл бұрын
Hi sir,Could you explain how to get x=5?
@discretemathvideos204
@discretemathvideos204 4 жыл бұрын
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.
@shimulbhattacharjee5137
@shimulbhattacharjee5137 5 жыл бұрын
Can I take x=3 ?
@discretemathvideos204
@discretemathvideos204 4 жыл бұрын
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.
@marcousosewelle5501
@marcousosewelle5501 4 жыл бұрын
3x^2 + 25/x2
@miguelcastorena4293
@miguelcastorena4293 3 жыл бұрын
thanks for the explanation
@bubblesgrappling736
@bubblesgrappling736 4 жыл бұрын
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
@discretemathvideos204 4 жыл бұрын
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
@dimakavetskyy2082 Жыл бұрын
YOOOOOOOOOOOOOOOOOOOOOO
@sameertrimade9691
@sameertrimade9691 5 жыл бұрын
horrible lecture
@decayedjollyrancher88
@decayedjollyrancher88 7 ай бұрын
make a better one or get out buddy. this is the reason i have a degree.
Algorithms: Big O Notation Examples 2
8:08
Discrete Math videos
Рет қаралды 141 М.
How to Prove or Disprove Big-O - Introduction to Computer Science
18:35
Would you like a delicious big mooncake? #shorts#Mooncake #China #Chinesefood
00:30
СҰЛТАН СҮЛЕЙМАНДАР | bayGUYS
24:46
bayGUYS
Рет қаралды 832 М.
Age 10-12 Math - 5.6 - Percentages in Word Problems
4:44
Moving Beyond the Page
Рет қаралды 188
1.8.1 Asymptotic Notations Big Oh - Omega - Theta #1
15:46
Abdul Bari
Рет қаралды 1,8 МЛН
Big-O Notation - For Coding Interviews
20:38
NeetCode
Рет қаралды 403 М.
Big-O notation in 5 minutes
5:13
Michael Sambol
Рет қаралды 1 МЛН
Discrete Mathematical Structures Spring 2022 Big O Notation
46:28
Dr. Randy Davila
Рет қаралды 9 М.
What Is Big O Notation?
17:45
Reducible
Рет қаралды 310 М.
Learn Big O notation in 6 minutes 📈
6:25
Bro Code
Рет қаралды 200 М.
Asymptotic Notation 3 - Example of Big O Notation
6:55
Professor Painter
Рет қаралды 23 М.