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!

Пікірлер: 48

  • @SN-ow1bp
    @SN-ow1bp8 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    8 ай бұрын

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

  • @purifynature8479
    @purifynature84799 ай бұрын

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

  • @shuyao5248
    @shuyao52483 күн бұрын

    finally well understand. Thank you very much

  • @QuocDatPhung

    @QuocDatPhung

    3 күн бұрын

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

  • @mes2914
    @mes29145 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    5 ай бұрын

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

  • @nandor2329

    @nandor2329

    3 ай бұрын

    Abssolutely agree, what a man, Thanks !!!

  • @punditgi
    @punditgi9 ай бұрын

    Excellent video! 🎉

  • @misspps_
    @misspps_3 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    3 ай бұрын

    I'm glad it was helpful! You can find the Big Ω video here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @josephsena5963
    @josephsena596313 күн бұрын

    This was really helpful, thank you

  • @QuocDatPhung

    @QuocDatPhung

    13 күн бұрын

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

  • @m3ga975
    @m3ga9754 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    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: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @liu.qiandao4194
    @liu.qiandao41944 ай бұрын

    that's what im looking for man!

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    I'm glad it helped! You can find all of my Computer Science videos here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @Pasquiz_
    @Pasquiz_4 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    You're very welcome! You can find all of my CS videos in this playlsit: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @Rootoo000
    @Rootoo0004 ай бұрын

    What a great channel !!😮💓💓

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    Thanks so much! You can find all of my CS videos here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @user-pk9ov6ek2b
    @user-pk9ov6ek2b3 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    3 ай бұрын

    Thank you! Don't forget to see my video on Big Omega! You can find the link here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @austinscott4695
    @austinscott46954 ай бұрын

    Thank you!

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

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

  • @suteguma0
    @suteguma03 ай бұрын

    bro is the GOAT

  • @QuocDatPhung

    @QuocDatPhung

    3 ай бұрын

    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!): kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @Simple-M___zzz
    @Simple-M___zzz14 күн бұрын

    thank yooooou

  • @QuocDatPhung

    @QuocDatPhung

    14 күн бұрын

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

  • @etcetera7529
    @etcetera75294 ай бұрын

    super video

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    Thanks so much! You can find all of my CS videos in this link here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @WolkenDesigns
    @WolkenDesigns2 ай бұрын

    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

    @QuocDatPhung

    2 ай бұрын

    I actually have videos on Big Omega/Theta! You can find it here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @nomnaday
    @nomnaday4 ай бұрын

    cảm ơn bạn ơi

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    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): kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @isaiahle9450
    @isaiahle94502 ай бұрын

    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

    @QuocDatPhung

    2 ай бұрын

    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: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @imjuszay1470
    @imjuszay14704 ай бұрын

    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

    @QuocDatPhung

    4 ай бұрын

    Yes that should be fine :) You can find all of my CS videos here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @mahrbooiiii
    @mahrbooiiiiАй бұрын

    I love you

  • @QuocDatPhung

    @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: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

  • @AbhishekVerma-kj9hd
    @AbhishekVerma-kj9hdАй бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    Ай бұрын

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

  • @seketorianGaming
    @seketorianGaming4 ай бұрын

    howd you get 2n + 3n

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    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

    @seketorianGaming

    4 ай бұрын

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

  • @QuocDatPhung

    @QuocDatPhung

    4 ай бұрын

    @@seketorianGaming No worries! You can find all of my Data Structures & Algorithms videos in this playlist: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC