Asymptotic Notations - The Three
Now, let’s formally learn the notations.
Asymptotic notations are notations used to describe the behaviors of the running time of an algorithm. There are three main notations, namely Big-O, Omega, and Theta.
Big-O notation, or O(running time), represents the upper bound. Omega notation, or Ω(running time), represents the lower bound. Theta notation, or Θ(running time), represents the average value or range.
Suppose
n is the input size(like a list of n numbers). Also, suppose c is some positive constant (like 1, 24, 4.5, 8, and so on). Then O(n) means that the algorithm you are analyzing takes no more than c*n operations, Ω(n) means that the algorithm you are analyzing takes at least c*n operations. Θ(n) means that the algorithm is both O(n) and Ω(n), meaning it is exactly c*n operations.As you can see here, the constants are ignored in asymptotic notations. We will get to why in the next section.
Previous Section
15.2 Why learn Asymptotic Analysis?Next Section
15.4 Rules for this CourseCopyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.