Not every notation represents a worst-case scenario
If you can’t read this fully. Click on the friend link.
Notations are of many types; the most basic and popular one known to novices and advanced programmers is the Asymptotic Notation. Asymptotic Notations’ popularity can be majorly attributed to its ease of analysis and predictive nature. If this sounds alien to you or if you have trouble determining best-case, worst-case or average-case scenarios, this read is for YOU.
To understand these notations first let us understand functions.
Functions are a form of relation between a set of inputs and a set of outputs where each input is mapped to one and only one output.
This means when functions are graphed on an x-y axis, you can find one and only one y-value for any x-value.
Back to Notations, for them to be graphically interpreted we take a set of functions which based on the notation work like threshold functions (you will get to know more about this in the next few parts) and another function, created by applying certain calculations to characterise the running times of the algorithm, who’s complexities are to be computed.
Theta Θ Notation:
This Notation presents the average case scenario where the algorithm function is recorded in a sandwiched fashion between two linearly combined functions(threshold functions) like c1g(n) and c2g(n). It can be said that for all N≥N₀ on the x-axis f(n) is asymptotically tight-bound by g(n) within a constant factor.
Mathematically this can be noted as,
C1⋅g(n)≤f(n)≤C2⋅g(n) ∀ N≥N₀ → f(n) = Θ(g(n))
Intuitively we can understand from the graph that this is an average-case scenario.
Oh O Notation:
O Notation represents the Worst-case scenario. Here the g(n) function serves as the upper limit of the function. As seen in the diagram, we only have an asymptotic upper bound. Here, the function at any n value greater than the threshold value(n₀) will always be less than the value presented by g(n)(asymptotic upper bound). Hence, the upper bound represents the tailor-made worst case for each n value of that function.
Now mathematically it can be stated as,
0≤f(n)≤C⋅g(n) ∀ N≥N₀ → f(n) ≤ O(g(n))
You may have heard of the terms Big O and Small o, they share a semblance in their functionality except for a minor difference.
Difference between Big O and Small O:
- The difference between Big O and small O notations is that big-O may be asymptotically tight while little-o ensures the upper bound isn’t asymptotically tight.
- Big O is similar to a closed interval case and Small O to an open interval.
- Better put, Big-O notation says that one function is asymptotically no more than another, while small-o notation says one function is asymptotically less than another.
Omega Ω Notation:
This is used to give the best-case scenario of a function. It has a lower bound, below which the function shows no y-value above the threshold point(N₀), highlighting the lowest possible value of a given function. Hence this symbolizes the best-case of a function. Here, the asymptotic lower bound is evident.
This can be mathematically formulated as,
C⋅g(n)≤f(n)≤0 ∀ N≥N₀ → f(n) ≥ Ω(g(n))
Key point:
• Every function used within Asymptotic Notations is asymptotically non-negative. As, all these notations inherently deal with non-negative functions. If you are wondering why they are so, it is because the growth rate of a function cannot be negative; it represents how the function’s output changes concerning the size of its input.
Conversion from Algebraic to Asymptotic:
This can be done by throwing away lower-order terms and ignoring the leading coefficient (A) of the highest-order algebraic term (A should not equal to 0).
For instance, c1 ≤ (3÷5) x⁴-55x³ -20x²-100x ≤ c2 can be written as Θ(n⁴) as all the lower order terms even with very high coefficients are insignificant with respect to the dominance of the highest order term when n has a high magnitude, here around 100. It can be estimated around n=100 that the curve is going to be dominated by the effect of n⁴ and will follow asymptotic behaviour.
Hence, with its ease in converting complex functions to asymptotic notations, it has become a popular go-to option for programmers to estimate the time complexity of a program with high accuracy. Prediction of the nature of the graph or the calculation of the N₀ too is possible with this system.
Hope this read gives you a better understanding of how asymptotic notations work. Thank You.
