Lecture 4: Sets, complexity, and Big O

Lecture 4: Sets, complexity, and Big O
  • Currently 4.0/5 Stars.
5045 views, 1 rating - 01:04:47
Part of video series ArsDigita Discrete Math Course
Taught by ArsDigita
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/
Learn all about sets and Big O Notation.
  • 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?
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.
  • Currently 4.0/5 Stars.
Reviewed by MathVids Staff on April 11, 2009.
 
Browse Store
App_store_badge Smart-logo