Hands-On Data Structures and Algorithms with JavaScript

Omega notation

Similar to the Big O notation discussed earlier, Omega notation denotes the lower bound rate of growth of the runtime of an algorithm. So, if we have a f(n) method, which we want to represent with a time complexity function (that is, a Set) g(n), then Omega notation can be defined as the following:

f(n) is O(g(n)) if and only if there exists constants c and n₀ where f(n) >= cg(n) where the input size n >= n₀.

Taking the same preceding example, we have f(n) = 4n + 1 and then g(n) = n. We will need to validate the existence of c and n₀ such that the preceding condition holds, as shown in the following snippet:

4n + 1 >= c * n , where n >= n0

We can see that this condition holds for c = 4 and n₀ = 0. Thus, we can say that our ...