Lecture 4: Sets, complexity, and Big O

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
10859 views | 1 rating
Lesson Description:

Learn all about sets and Big O Notation.

More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/

Additional Resources:
Questions answered by this video:
  • What is a set in Discrete Mathematics?
  • What is diagonalization and how can it be used to prove that a set is countable or uncountable?
  • What is bubble sort, how does it work, and how much time does it take?
  • What is Big O notation and how do you write that something is of a certain order?
  • What is Omega notation and Big Theta notation?
  • How can you show that something is O(n^2)?
  • How can you find and prove the order or complexity of a function?
  • What are some algorithms for sorting and what is their complexity?
  • What is the limit for the best possible sorting time?
  • Where does O(log n!) fit into the order of complexity for functions?
  • How can you prove that log n! <= log n^n = n log n?
  • Staff Review

    • Currently 4.0/5 Stars.
    This lesson is all about finding the order or complexity of functions and processes using Big O, Omega, and Big Theta notation. Sorting and other algorithms are covered. Several proofs and computations are shown and explained. This is very useful for those interested in computer science algorithms and their complexities.