15.3 Asymptotic Notations - The Three

Asymptotic Notations - The Three

Write some stuff here. Heading 1 should be highlighted yellow and underlined.

Now, let’s formally learn the notations.

Asymptotic Notations are notations used to describe bounding behavior on 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 upper and lower bounds.

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

Next Section


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