What is the difference between Θ(n), Ο(n) and Ω(n)?
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
app
.gitignore
README.md
package.json
server.js

README.md

Class: Running Time and Asymptotic Notation

Computer Science


Do you ever feel like you never completely understood asymptotic notation and running time analysis? What exactly is the difference between Θ(n), Ο(n) and Ω(n)? In computer science, asymptotic analysis is used to compare the relative performance of different algorithms. The symbols used to represent these running times come from mathematics and have specific meanings. But usually the explanations in lectures and textbooks are really dense! I'm hoping this class gives you an intuitive idea of how it works and removes the mystery. If you're a software engineer you'll come across these concepts eventually, whether you're in school or building the next big framework.

What's in this class?

  • A Message From Chris - I'd like to give you a quick reason I decided to do this class. I'd like your feedback on whether this type of material is helpful. Please leave a comment in the comment box!

  • What is Running Time? - In this video you'll learn what is meant by the phrase "running time." We'll come up with an expression for the running time of a simple JavaScript function.

  • Understanding Constants - Instead of picking actual times for the execution of statements we can just represent those times with variables. It works since we're usually comparing the performance of one algorithm relative to another. In this video we'll replace the exact constant times we picked randomly in the last video, to variables to represent those times.

  • Asymptotic Growth - There are some estimating shortcuts we can take for analyzing algorithms. If the size of the input (think size of an array) is large enough (really really large) we can just remove the constants and keep the highest order term. It feels like cheating but it works because the lower order terms and constants end up being completely dominated by the highest order term for large inputs. This video should make it more intuitive!

  • Common Functions and Their Graphs - You'll hear a lot about certain math functions that come up over and over again. In this video I'll show you what those functions look like so when you see them in symbol form you can form a picture in your mind. I'll cover linear, polynomial, exponential and logarithmic functions and their graphs. And I'll spend a little extra time on logarithms just in case your algebra is a little rusty.

  • Asymptotic Notation - Asymptotic notation can be used to describe running times. You'll often hear the terms Big-O, Theta, and Omega of some function. But what exactly is the difference between these symbols? What do they represent? Before jumping into a mathematical definition let's get some intuition.

  • Defining Theta Θ(g(n)) - In computer science textbooks you'll see very precise, mathematical definitions for theta, omega and big-o. In this video I'll show you what the definitions mean and you'll see an example of applying the definition of theta to a simple linear function. In asymptotic notation, theta means equal to (==).

  • Defining Omega Ω(g(n)) - Now that you have a feel for the mathematical set notation, let's apply it to defining omega. Omega means greater than or equal to (>=) in asymptotic notation.

  • Defining Big-O Ο(g(n)) - Finally, let's formally define the Big-O notation. This is the one you'll see most often and it means less than or equal to (<=) in asymptotic notation.

  • Analyzing Algorithms - Let's look at some examples of how to apply asymptotic notation to a few JavaScript functions. You'll see how all three symbols can be used to describe a function like printList.