Prove Big-O

[@WebDevAnjali]

literally watched a dozen of video still couldn't understand the how to write it down a clear proof....You're the only person who did it .... A BIG thanks to u man... u r a life saver

[@randerson112358]

Thanks Anchal, I appreciate it and I had similar troubles when I was first learning this stuff.

[@khr1395]

The ONLY person who has just explained this and walked through it clearly is you. Thank you. I swear every single "example" (used very loosely) I've seen before this rushes through it and doesn't explain anything. Thank you for being clear and easy to follow.

[@oreogunleye3557]

8 years since this video dropped and it helped me work through big O. Thank you!

[@Alreeshid]

I want to thank you for making this video. Proofs hit me out of nowhere and made no sense to me. This video gave me a much better understanding than anything else I found, and you've helped me find my footing because of it. Truly, thank you

[@randerson112358]

Thanks for the comment Alreeshid ! I truly appreciate it !

[@AndrewThacker]

Thank you! Professors always manage to make the material out to be much more difficult than it actually is. This was extremely helpful

[@randerson112358]

Yes I understand that frustration, it makes me wonder sometimes if they truly understand topic.

[@caialyu2833]

@@randerson112358 SO TRUE! Seems like they are just making it extra difficult and abstract sometimes

[@DueceBigelow]

Finally! I spent days trying to find something to explain this because i could not connect the info in my book. It simply showed the same function that you started with and then the conclusion. asked some math majors and EE engineers I work with, couldn't figure out how the book went from start to finish either. So thank you very much

[@BlazedOutTurtle]

Finally makes sense ! currently studying this for my algorithms final, you are a life saver man

[@randerson112358]

+BlazedOutTurtle , thanks glad this video helped !

[@adefemie.kolawole9336]

i can't believe you explained this concept this simply. Thanks to infinity.

[@randerson112358]

Glad you liked it man !

[@brick_videos]

just switching the big o formula around so it becomes a ratio simplifies this so much. my exam in the morning thanks you

[@amaliakhaerunnisa7253]

the best, simplest, and clearest explanation ever. thank u

[@robertwagner3909]

This is the best explanation I've found so far on this topic

[@randerson112358]

Thanks !

[@AliMalik-yt5ex]

This is fantastic. Was just staring blankly at my prof's explanation and it didn't really help me. This is the first video I found that actually made it easy to understand. This will really help me in my mid term upcoming in the next two weeks.

[@randerson112358]

Glad it helped!

[@HeavensHeros12]

I'd been struggling to understand this topic, and none of it made sense until I came across your video. Thanks so much for the explanation! :)

[@randerson112358]

Hey ! Thanks I am glad this video could help.

[@elcar5468]

I've been struggling to understand what values to make n and the constant. Nice to see a clear demonstration on why you arrived at n = 4 for the proof unlike many other resources I've looked at.

[@oksanasakhniuk617]

Read the book, couldnt get it. Watched your video, everything became clear. Thanks a lot for great explanation.

[@randerson112358]

Thank you for watching, the text books can be a bit hard to understand at times.

[@jupiterscreams]

Great video.

[@BlueKaiTheEnd-]

OOh My god! This just made things clear! Been re-reading my textbook trying to understand this concept all week. But this video helped me finally understand big-o proof in a matter of minutes. Wish I found this sooner. Thanks!

[@nathannelson2710]

R. Anderson, thank you for the step-by-step explanation! I will definitely be checking out more of you videos.

[@charleswillian5577]

Thank you! I couldn't understand until I saw your video

[@mossthebryophyter]

Thank you. I'm struggling in online school and this is a big help

[@randerson112358]

Glad the videos help!

[@user-ji7fd3wc5b]

Omfg thank you! Idk why KZbin doesn’t recommend you. Literally just saved my ass since my professor doesn’t teach shit

[@randerson112358]

Thanks, hopefully KZbin will eventually start recommending some of my videos that are helpful for others.

[@user-ji7fd3wc5b]

@@randerson112358 I really like your videos, also would you be interested if in tutoring via zoom if I paid you. The class is Algorithm techniques

[@kikilido9346]

You're awesome for this! You made it so simple! Thank you so much for making this 9 years ago lmao! Wish me luck for my test today!

[@randerson112358]

Good luck!

[@saberdino966]

Thank you so much. I've been struggling with Big O notation and pulling my hair out trying to figure it out. Nothing has helped clear the fog. The text book just didn't make sense nor did any of the other material I've read online. This is the first video that actually made sense to me.

[@randerson112358]

+saberdino966 No problem , I definitely understand your frustration. I could barely understand the material in my classes, and had to go and ask other professors, and students to give me some clarity on this subject. Keep learning this stuff and any computer science topic, it only gets better and more interesting. I really enjoy this field. randerson112358

[@anshul4608]

thank you, this is the only explanation that I found that actually helped.

[@SilkySmooth976]

Thanks man helped clear things up right before my test!

[@AviPars]

please do more proofs and explanations especially the complex ones

[@randerson112358]

Thanks for the comment, I may do more complex proofs in the future.

[@efromthestudio]

Bro I was just about to give up hope then I foiund this!! Thank you

[@DatDaDatty]

so much better than my teacher

[@markzayat725]

This was a godsend man, thanks so much!

[@nuse420]

Dude this is awesome! You spell it out very well. Thanks, this was a breakthrough for me.

[@KeithAdam]

great explanation

[@jonphy2370]

holy shit ,it was a great pity that i find your video so late .i had just failed my exam ,but after your tutorial I think i can get it.

[@briancain7544]

Thanks Man this relay helped me! I wish you the best of Life!

[@randerson112358]

+Brian Cain thank you!

[@naufal4139]

thank you too randerson112358

[@DaemonMunkir]

You are a life saver. Thank you so much.

[@DalePollitt]

Appreciate it, this helped a lot. I actually had to prove an almost identical problem.

[@randerson112358]

+Dale Pollitt that's great hear!

[@ac3_train3r_blak34]

A true voice of reason out of nowhere.

[@randerson112358]

Thanks!

[@raphaelcarvalho4288]

How did you transform (n^2 + 2n + 1) / n^2 (n^2 + 2n + 1) / n^2?

[@randerson112358]

Raphael S Carvalho , good question, in this video I took a short cut for time and showed that (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 for all n > 1 which is true. There was NO transforming of the original equation from (n^2 + 2n + 1) / n^2 (n^2 + 2n + 1) / n^2, it was a statement or a fact that (n^2 + 2n^2 + n^2) / n^2 is ALWAYS greater than (n^2 + 2n + 1) / n^2 whenever the value 'n' is greater than 1. You can see the value on the left hand side grows faster when you add larger and larger values for n. For EXAMPLE: let n = 10 Then the inequality equals the following by substitution: ORIGINAL inequality: (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 After Substitution: (10^2 + 2(10^2) + 10^2) / 10^2 > (10^2 + 2(10) + 1) / 10^2 Now to simplify: (100 + 200 + 100) /100 > (100 + 20 + 1)/100 = (400)/100 > (120)/100 = 4 > 1.2 which is TRUE Now let's use a bigger number like 50: Let n = 50 Then the inequality equals the following by substitution: ORIGINAL inequality: (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 After Substitution: (50^2 + 2(50^2) + 50^2) / 50^2 > (50^2 + 2(50) + 1) / 50^2 Now to simplify: (2500 + 5000 + 2500)/ 2500 > (2500 + 100 + 1) / 2500 = (10000)/2500 > (2601)/2500 = 4 > 1.0404 which is TRUE Notice that the value on the left always equals 4 as the value 'n' increases, and the value on the right gets smaller as the value n increases, this shows the function on the right hand side will always be less than the number 4 as long as the value n is greater than 1. NOW for your question, which I believe you meant is, how do I know that the second function (n^2 + 2n^2 + n^2) / n^2 is ALWAYS greater than (n^2 + 2n + 1) / n^2, and the simple answer is by doing an algebra proof or using intuition. The intuition and proof are below: Intuition: If I have a number (a constant) divided by a variable, the over all value of that number will always decrease, because n grows faster than a constant. A constant doesn't grow at all. For Example 1/n will always be less than or equal to 1(a constant) whenever n is greater than or equal to 1. function: 1/n let n = 1, function = 1/1 = 1 let n = 2, function = 1/2 = .5 let n = 3, function = 1/3 = .333... let n = 4, function = 1/4 = .25 so the constant value that 1/n will never be greater than is 1, whenever n is greater than or equal to 1. Hence: 1/n = 1 second example: Here I will use a denominator that grows faster then it's numerator like the above example: function: (n+1) / n^2 let n = 1, function = (1 + 1) / 1^2 = (2)/1 = 2 let n = 2, function = (2 + 1)/ 2^2 = 3/4 = .75 let n = 3, function = (3 + 1)/ 3^2 = 4/9 = .44444..... so the constant value that 1/n will never be greater than is 2, whenever n is greater than or equal to 1. Hence: (n+1)/ n^2 =1 So this means for my orignal function '(n^2 + 2n + 1) / n^2', as long as the denominator is the biggest possible value or grows the fastest there is a constant that the function will be less than, in the above cases, that constant is a 1 for example 1 and 2 for example 2. OKAY HERE IS YOUR ANSWER: By making every number in the numerator divisible by the denominator (AKA the highest possible value) we get a constant that the original function is less than. From example 1, the function 1/n will never be greater than 1 By using the above principle (making the numerator a multiple of the denominator) we can see this is true. Ex1: Original = 1/n Transformation = n*(1) / n = n/n = 1 (The constant that the function will never be greater than) Hence: n/n > 1/n whenever n > 1 Ex2: Original = (n+1)/n^2 (Notice both n and 1 grow slower than n^2) Transformation= (n^2 + n^2)/ n^2 = 2(n^2)/n^2 = 2 (The constant that the function will never be greater than) Hence: (n^2 + n^2) / n^2 > (n+1)/n^2 whenever n > 1 and so it follows to find a constant that our original function will always be less than we need to do a similar 'transformation' Ex3:Original = (n^2 + 2n + 1) / n^2 Transformation = (n^2 + 2n^2 + n^2) / n^2 = 1 + 2 + 1 = 4 So 4 is the constant that (n^2 + 2n + 1) / n^2 will always be less than whenever n > 1. Few, last proof this is always true Using the inequality:(n^2 + 2n^2 + n^2) / n^2 >= (n^2 + 2n + 1) / n^2 , and n >=1 1) Multiply both sides by n^2 to get the below: (n^2 + 2n^2 + n^2) >= (n^2 + 2n + 1) whenever n >= 1 2) Subtract n^2 from both sides to get the below: ( 2n^2 + n^2) >= (2n + 1) whenever n >= 1 3) Subtract 1 from both sides to get the below: (2n^2 + n^2 - 1) >= (2n) whenever n >= 1 4) Subtract 2n from both sides to get the below: (2n^2 + n^2 - 1 - 2n) >= 0 whenever n >=1 5) Add like terms and rearrange to get the below: (3n^2 - 2n - 1) >= 0 whenever n >= 1 6) Divide both sides by n^2 (3 - 2/n^2 - 1/n^2) > 0 , whenever n >= 1 Note: 2/n^2 is always less than or equal to 2 and 1/n^2 is always less than or equal to 1 whenever n increases since the smallest value n can be is 1 7) Rewrite the equation as the maximum values 2/n^2 and 1/n^2 can be (3 - 2 - 1) >= 0 ==> (1-1) >= 0 ==> 0 >= 0 which is always true. I hope this spreads some light on the reason why I said (n^2 + 2n^2 + n^2) / n^2 >= (n^2 + 2n + 1) / n^2 , and n >=1 randerson112358

[@dynamohack]

is there any short explaination

[@TastyLaserCakes]

Your in depth explanation of this rocks!! Thanks for taking the time. It was exactly what I wanted to know.

[@luisojedaguzman7624]

@@dynamohack Consider a simplier example where we know that n²/n² is always ≥ to n/n² for all n ≥ 1.We can use this fact to find an upper bound that suggest that n²/n² = 1 thus 1 is always ≥ to 1/n² for all n ≥ 1. In a similar fashion (n²+2n²+n²)/n² will always be ≥ to (n²+2n+1)/n² for all n ≥ 1. By breaking (n²+2n²+n²)/n² into independent fractions we get n²/n² + 2n²/n² + n²/n² simplifies to 1+2+1=4 thus 4 is always ≥ to (n²+2n+1)/n² for all n ≥ 1.

[@dynamohack]

@@luisojedaguzman7624 i cleared my exam 2 years ago thank you

[@mdog077]

Dude you're a lifesaver and a saint!!

[@randerson112358]

Thanks!

[@samuelhailai2168]

wow, you make it super cool, keep it up bro.

[@randerson112358]

+Samuel Hailai thanks

[@Zach-bi7bq]

You the real MVP.

[@randerson112358]

Haha thanks !

[@snarf45]

This is so helpfull, Thank you!

[@randerson112358]

Thanks for watching!

[@mattgarbeil5922]

This is bad ass!! Thanks a million. Whoever gave the two thumbs down. Whack!!!

[@avibank5115]

Since ...

[@Jedibob5]

Hey, look, another R. Anderson! Thanks for the vid, it's definitely helpful to see this kind of thing worked out step by step.

[@randerson112358]

Thanks

[@RabeeQiblawi]

Thank you a lot man really helpful video

[@andrewowusu279]

This is the best explanation of big-oh I have seen so far. Thank you very much for saving a student from committing suicide( just kidding). You are great

[@randerson112358]

Lol yeah proving big oh was tough for me to understand as a undergraduate .

[@Luingus]

what do you do when you are given a logarithmic function?

[@gregsmith80]

Awesome video. This really helped clear some things up for me. I see that you have some other videos up, which is great. If I could make one request, please put your camera on a tripod or some stable surface. I'm sure that I'm a fringe case, but the slight wobble of the video is enough to make me motion sick.

[@randerson112358]

thanks, I plan on getting something to make my camera stable

[@kenwoz2778]

At about 1:48 you say: We want to find a function bigger than this one. Why is that? Why do you replace everything that's not n^2 with n^2? What's the logic behind it? I've seen it in other problems being solved and I still don't get it. Thanks!

[@randerson112358]

The reason for the bigger function is to derive a constant called C that will satisfy the equation which is f(n) / g(n)

[@monicaquiros6504]

Thank you. This explanation helped me a lot. :)

[@5137404]

My text book is garbage this semester, wish I would of found this video sooner.

[@onixz100]

But how did you know to choose k = 1? Why wasn't it k = 8, or k = 6? Or some other number? What made you choose that? Please explain your thought process.

[@randerson112358]

Hi Veritas, I could've chosen k= 8 or k=6 or k= 89 or k = 100000 , as long as k is some number greater than 0. Notice that in this video if k=8 then it still satisfies the big oh definition, since I chose values of n >= 1 this implies values of n>=2 and n >= 3 and so on. So I think you may be a little confused as to what k is and why do we need it in the definition to prove big-oh. The definition of Big-Oh: A function f(n) is said to be O( g(n) ) if there exist two positive constants C and k that will make the following equation true; f(n) k The value of k replaces the input value n, in the function. For example Let f(n) = n^2 and let g(n) = n^3 Let's create a chart for the vaues of n n | f(n) | g(n) ------------------------- 0 | 0 | 0

[@gabrielvilela8563]

Thank you so much for this video!

[@willmfftt]

Great explanation! Thank you

[@randerson112358]

Thank you very much !

[@baileyworks6119]

This video is awesome, thank you so much!

[@randerson112358]

Thanks for watching !

[@abovetheinfluence555]

Thanks! I can't find this explanation anywhere

[@cindyjane9062]

Great explanation!

[@randerson112358]

Thank you Cindy !

[@ricardomuller2066]

8 years ago randerso112358 woke up and decided to save my homework from today

[@alexiannuzzi9640]

Thanks so much, helped a lot.

[@randerson112358]

Great to hear!

[@Horrortelltales]

Can you simplify the equation and do the same calculation and proof?

[@Mangosrx]

Extremely helpful. Thank you so much!

[@randerson112358]

Thanks, this was a topic I used to struggle with as well. I am glad that I can help someone else !

[@Nova-Rift]

At 2:33 you say for all n greater than 1, but then you pick 1 as your input and then say 4 is greater than the right side. Don't you have to pick a number greater than 1 for that to make sense? Try plugging in 1 to both sides of that inequality, you'll see that you get, 4 > 4, which is not true.

[@green_razor8569]

Why the hell does my textbook use this complicated algebra when this method is so much easier? School sucks man i hate this. Thank u

[@budstawudsta9115]

very helpful thanks!!

[@lindamc466]

do you also have a video to proof f e O(g) is equivalent to g e O(f)?

[@tsionketema7826]

Thank you so much bro!!!

[@Louskiuk]

Thanks, great help

[@vantazaiom4799]

Thanks.. It was helpful a lot 👍🏼

[@PatrickWang565656]

Thanks! It's so helpful for me ~~

[@diegobenalcazar4836]

you can solve it much easier considering the limit when n goes to infinite, right? I am still learning but I think the limit must be a constant for it to be big O

[@JovaCoder]

Thanks for this!

[@randerson112358]

Jovaughn Lockridge Thank you for watching

[@ahmedatta515]

great thanks , I have a question what is(k) as c or they are different

[@yukihiroshibato7142]

thank you sooo much!

[@dovidsamuels5709]

In this case wouldn't f(n) be big-theta of g(n)? If C was 1 then f(n) > g(n) for all n > 1.

[@FlowGG3594]

at 2:30, why do you make it n > 1 instead of n >= 1?

[@gwenythjpw]

At 2:30 why did you decide on n>1, not n>=1? Thanks for the very helpful video

[@randerson112358]

I chose n > 1, because it makes the overall statement true.

[@kaylielepley2251]

What if instead of the constant at the end being 1, it's a bigger number? Say 100, then instead of n^2 would it just be 100n^2

[@nathanportela1956]

THANK YOU SO MUCH!

[@randerson112358]

Thanks for watching!

[@yanca6830]

THANK YOU

[@randerson112358]

Thanks for watching!

[@qingen7005]

Thank you for the video. Do you always use the value 1 for constant?

[@randerson112358]

+Made Different thank you and not always.

[@qingen7005]

Sorry I might have phrased my question wrongly. What I meant was do we always use n >= 1? I have seen many examples online and all uses the value 1 but I do not understand why 1.

[@randerson112358]

+Made Different the answer is no. You can use any other constant you want.

[@qingen7005]

Okay noted. Thank you for your reply. Cheers!

[@KiloWhiskay]

At 3:54, how does proving: (n^2 + 2n + 1) / (n^2) = 1 Mean that f(n) = O( g(n) )?

[@randerson112358]

+Kenny Worden All we had show is f(n) = k this proves f(n) is O( g(n) ) Rewrite the equation/ definition to get the below: f(n) / g(n) =k to prove f(n) is O( g(n) ) In this example : f(n) = (n^2 + 2n + 1) g(n) = (n^2) C = 4 k = 1 Notice as the value of n increases noted by n>=1, the value of f(n) /g(n) decreases. Specifically if you plug in any value for n that is greater than 1, then (n^2 + 2n + 1) / (n^2) will always be less than or equal to 4. NOTE: if you don't see this then plug in values for 'n' and you will notice that (n^2 + 2n + 1) / (n^2) will get smaller and smaller as n gets bigger. For example plug in n=1, then n=2, then n=3 and so on until you see the decreasing pattern. So since we proved the statement f(n) / g(n) =k is true, we proved f(n) is O( g(n) ). or more specifically Since we proved (n^2 + 2n + 1) / (n^2) = 1 is always TRUE , We proved (n^2 +2n + 1) is O( (n^2) randerson112358

[@clarcktumazar]

how did you get the number 4???

[@ythalorossy]

Thanks for share, man.

[@vojka2973]

thank you man...

[@randerson112358]

Funky Attitude thanks

[@xking21]

Thanks!

[@Rawoonah2cool]

thank you.

[@grant9855]

gotta love paying thousands of dollars to go to hours of lectures only to have to watch 3 minutes of a youtube video of a dudes whiteboard in 2014 to learn this

[@momohalo3977]

I'll watch the playlist of Algortithm analysis of this chanel because I am taking Algorithms II when i didn't went to Algorithms I xd

[@DarthStalkers]

Great work! Youre awesome :D

[@krishanudev7573]

Thank you so much to help out

[@sarahbates4544]

You're wonderful!!!

[@uzomaohajekwe7149]

Why did you choose 1 for k?

[@Chandler890]

What about logs, trig, fraction. ...

[@pandalover555]

OMG THANK YOU

[@thefreelancerider69]

pls can u explain the second step din't get it

[@user-tm1ix7xi1n]

How would i do if my g(n) is 3n^4+6n^2+8n+2 and f(n) is 8n^3+4n^2+5n+1. Would you please guide me through it.

[@nandanapradeep7540]

is value of c and k unique

[@marlonathomas]

Thanks! You rock!

[@AreaSlidin]

How do you know that g(n) is n^2?

[@DeHub94]

4:00 No! Why did you remove that? I wasn't done writing it down...

[@randerson112358]

+Mira Bellenbaum lol pause the video about 3 seconds before then 4:00