### 1 video in "Complexity"

## Lecture 4: Sets, complexity, and Big O

Lecture 4: Sets, complexity, and Big O

6960 views, 1 rating - 01:04:47

Part of video series ArsDigita Discrete Math Course

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/

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

(
download video
)

Learn all about sets and Big O Notation.

- Lecture Notes - Lecture Notes from the course
- Problem Set 2 - A problem set with some problems from this lecture
- Problem Set 2 Solutions - Solutions to the Problem Set

- 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.