Asymptotic Notation
Learn Big-O notation and how to determine the complexity of algorithms.
Start
Key Concepts
Review core concepts you need to learn to master this subject
Big-Θ Notation
Asymptotic Notation
Adding Runtimes
Algorithmic Common Runtimes
Big-O Notation
Big-Ω Notation
Analyzing Runtime
Queue Versus Stack
Big-Θ Notation
Big-Θ Notation
We compute the big-Θ of an algorithm by counting the number of iterations the algorithm always takes with an input of n. For instance, the loop in the pseudo code below will always iterate N times for a list size of N. The runtime can be described as Θ(N).
Asymptotic Notation: Conceptual
Lesson 1 of 1
- 1Cheetahs. Ferraris. Life. All are fast, but how do you know which one is the fastest? You can measure a cheetah’s and a Ferrari’s speed with a speedometer. You can measure life with years and month…
- 2The first subtype of asymptotic notation we will explore is big Theta (denoted by Θ). We use big Theta when a program has only one case in term of runtime. But what exactly does that mean? Take a …
- 3Before we delve into the multiple runtime cases, let’s see the different common runtimes a program could have. Below is a list of common runtimes that run from fastest to slowest. - Θ(1). This…
- 4Sometimes, a program may have a different runtime for the best case and worst case. For instance, a program could have a best case runtime of Θ(1) and a worst case of Θ(N). We use a different notat…
- 5Sometimes, a program has so much going on that it’s hard to find the runtime of it. Take a look at the pseudocode program that first prints all the positive values up to N and then returns the numb…
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory
Asymptotic Notation
Start