Lecture 4: Sets, complexity, and Big O
10977 views
|
1
rating
Lesson Summary:
In this lesson, you'll learn about sets and Big O Notation. Specifically, the instructor goes over how to count all the scheme programs using diagonalization, and how there are things that you want to compute that there are no programs for. The instructor also introduces the concept of measuring how fast functions are growing, which is fundamental in algorithms, and demonstrates an example of calculating how many steps a sorting program takes.
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:
- 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
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
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.
