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!