How to Prove or Disprove Big-O - Introduction to Computer Science

In this video, I will show you how to prove or disprove Big O. I will also go over the formal definition of the formula Big O using asymptotic notation to determine the runtime of an algorithm. For example, you are asked to prove that a function 2n+3 is O(n). By the definition of big O, f(n) is O(g(n)) if you can find a positive constant c and a positive integer nₒ such that f(n) is less than or equal to c times g(n), for all n is greater than nₒ.
Knowing how to prove that something is Big O or not Big O is an important skill that Computer Science CS and Math students need to know about time complexity and growth of functions. It is likely that you will encounter this topic in your typical Data Structures, Discrete Mathematics, or Analysis of Algorithm courses at University.
I will also how you how to prive Big Omega Ω or Big Theta θ. If you enjoyed this video, please don't forget to comment down below and also subscribe if you haven't already!

[@SN-ow1bp]

youre the best tutor in the game for computer science & math, please don't stop making these videos

[@QuocDatPhung]

Thanks very much! I will never stop making videos :)

[@garubahabeeb1013]

This video was great, really liked the way you simplified each step and made it easy to understand 👍

[@QuocDatPhung]

Thank you Garu! Please kindly share with your friends and subscribe to support me ~ you can find all of my CS videos in this link: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@mes2914]

So much helper than a lecture in colleage,much straightforward,i will recommend to my classmate,thanks!!!

[@QuocDatPhung]

Thanks so much! Please also kindly subscribe! You can find all of my Data Structures and Algorithm lessons in this playlist: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@nandor2329]

Abssolutely agree, what a man, Thanks !!!

[@purifynature8479]

Thank you so much! This is what I was looking for.

[@punditgi]

Excellent video! 🎉

[@misspps_]

1.50 mins and I'm finally understand the concept. Thank you so much!

[@QuocDatPhung]

I'm glad it was helpful! You can find the Big Ω video here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@shuyao5248]

finally well understand. Thank you very much

[@QuocDatPhung]

Thank you for your kind words Shuyao! Please kindly share with your friends and subscribe ~ all of my CS videos are in this link: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@m3ga975]

Than you so much you made it so easy to understand how to do the formal way.

[@QuocDatPhung]

Thanks so much M3ga! I will try to work on Big Omega and Big Theta once I finish my exams haha. Please don't forget to subscribe! As well, you can find all of my Data Structures & Algorithms videos in this playlist: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@josephsena5963]

This was really helpful, thank you

[@QuocDatPhung]

You're welcome Joseph! Please kindly share and subscribe~ you can find all of my CS videos in this link: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@user-pk9ov6ek2b]

Bro, I have an exam in couple of days and you saved me, may god bless you

[@QuocDatPhung]

Thank you! Don't forget to see my video on Big Omega! You can find the link here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@Pasquiz_]

Thank you very much for making me understand this thing!!!😭

[@QuocDatPhung]

You're very welcome! You can find all of my CS videos in this playlsit: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@liu.qiandao4194]

that's what im looking for man!

[@QuocDatPhung]

I'm glad it helped! You can find all of my Computer Science videos here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@austinscott4695]

Thank you!

[@QuocDatPhung]

You're welcome! You can find all of my CS videos in this playlist (don't forget to share and kindly subscribe!): czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@Rootoo000]

What a great channel !!😮💓💓

[@QuocDatPhung]

Thanks so much! You can find all of my CS videos here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@nomnaday]

cảm ơn bạn ơi

[@QuocDatPhung]

Không có gì bạn! Bạn có thể tìm tất cả clip của mình về Computer Science trong link này nhé (bạn đừng quên chia sẻ và đăng kí hihi): czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@Simple-M___zzz]

thank yooooou

[@QuocDatPhung]

You're welcome Muhammed! Please kindly share and subscribe~ you can find all of my CS videos in this link: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@etcetera7529]

super video

[@QuocDatPhung]

Thanks so much! You can find all of my CS videos in this link here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@suteguma0]

bro is the GOAT

[@QuocDatPhung]

Thanks so much Thiên Phúc! I'm working on the one for Theta and Omega; you can find all of my CS videos in this playlist here (don't forget to share and kindly subscribe!): czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@WolkenDesigns]

Hi thank you for your video. To prove big Theta, do I have to prove big O and big Omega and if both are true big Theta is proved?
Also could you tell me following:
The way to find a constant c, we are choosing the one that we are trying to proove (for example xxx = O(n²). So on the right side of "is larger or equal than) all of the values will have to be larger than on the left side but max. as n².
What happens if we cannot choose a larger one by this definition? So if it is
100n³ = O(n²) we cannot choose n² as the largest.
Many thanks from Germany!!

[@QuocDatPhung]

I actually have videos on Big Omega/Theta! You can find it here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@imjuszay1470]

For the 5n^2 + 3nlogn + 2n + 5 is O(n^2)
I got constant C = 12 because instead of raising nlogn to n^2 I just dropped it all together
5n^2 + 3nlogn + 2n + 5

[@QuocDatPhung]

Yes that should be fine :) You can find all of my CS videos here: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@isaiahle9450]

Hi could I ask what n not is? In our class we use C and K but I find your method to be easier.

[@QuocDatPhung]

N not is the same as k :) some textbooks use different variables but they mean the same thing! Also I'm really glad to hear that you find my method easier! I would really appreciate if you could kindly share or subscribe ~ you can find all of my CS videos in this link: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@mahrbooiiii]

I love you

[@QuocDatPhung]

Thank you! I have videos on Big Theta and other topics too! Pls don't forget to share with your classmates and kindly subscribe ~ you can find all of my CS videos in this link: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@seketorianGaming]

howd you get 2n + 3n

[@QuocDatPhung]

Hi Timmy, please let me know the timestamp of the question you're referring to.

[@QuocDatPhung]

Do you mean the one at 1:12? Ok, now imagine you're in a math class. Let's say you have f(x) = x and g(x) = x^2. Since g(x) is quadratic, and f(x) is linear, then it must be that g(x) > f(x) meaning g(x) will at some point intersect f(x) and be above it forever. Agreed? You can also pick g(x) = x^3 or whatever you want and g(x) is still greater than f(x). Now, coming back to 1:12, let's say f(x) = 2n + 3. Can we find a function greater than this one? Yes. We can say the function 2n + 3n or 2n^2 + 3 or whatever you want. But for the sake of simplicity, let's pick 2n + 3n. Therefore, you get 2n + 3 < 2n + 3n. Does that make sense? Don't overcomplicate it. It's easier than it looks.

[@seketorianGaming]

@@QuocDatPhung Thank you, this helped. And you're correct I think I over complicated it.

[@QuocDatPhung]

@@seketorianGaming No worries! You can find all of my Data Structures & Algorithms videos in this playlist: czcams.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@AbhishekVerma-kj9hd]

Don't you think c^n is bigger than n^c

[@QuocDatPhung]

Yes, in the video I said that c^n is bigger than n^c at 5:20