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

Quoc Dat Phung
Quoc Dat Phung
16,278
0
Published 2023-10-07
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!
All Comments (21)
  • @SN-ow1bp
    youre the best tutor in the game for computer science & math, please don't stop making these videos
  • @mes2914
    So much helper than a lecture in colleage,much straightforward,i will recommend to my classmate,thanks!!!
  • @misspps_
    1.50 mins and I'm finally understand the concept. Thank you so much!
  • @m3ga975
    Than you so much you made it so easy to understand how to do the formal way.
  • @Pasquiz_
    Thank you very much for making me understand this thing!!!😭
  • @Rootoo000
    What a great channel !!😮💓💓
  • @user-pk9ov6ek2b
    Bro, I have an exam in couple of days and you saved me, may god bless you
  • @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!!
  • @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 <= 5n^2 + 2n ^2+ 5n^2 5n^2 + 3nlogn + 2n + 5 <= 12 * n^2 for all n >= 1 5 + 0 + 2 + 5 <= 12* 1 12 <= 12 for all n >= 1 Would this logic still work even though I came to the answer by a different means?
  • @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.