Hands-On Data Structures and Algorithms with JavaScript

Theta Notation

Having calculated the upper and lower bound rates of growth of our function f(n), we can now determine the tight bound or theta of our function f(n) as well. So, if we have a f(n) method, which we want to represent with a time complexity function (also known as a set) g(n), then the tight bound of a function can be defined as follows:

f(n) is O(g(n)) if , and only if , there exists constants c and n_0, where c₁g(n) < = f(n) <= c₂g(n) where the input size n >= n₀

The preceding operation, from the previous two sections, is already calculated for our function, that is, f(n) = 4n + 1: the value of c₁ = 4 , c₂ = 5, and n₀ = 1.

This provides us with the tight bound of our function f(n) and, since the function always lies within the ...