Page 30 - DCAP407_DATA_STRUCTURE

Unit 2: Complexity Analysis

Figure 2.2 shows Omega notation.

Figure 2.2: Omega Notation f(n) = Ώ (g(n))

Source: Puntambekar, A., A. (2010). Design and Analysis of Algorithms, First ed. Technical Publications Pune. Page.
23.
Let us take an example to understand the Omega notation more clearly.

Consider function f(n) = 2n2+5 and g(n) = 7n.
We need to find the constant c such that f(n) ≥ c∗ g(n).
Let n = 0, then
f(n) = 2n2+5 = 2(0)2+5 = 5
g(n) = 7(n) = 7(0) = 0
Here, f(n)>g(n)
Let n = 1, then
f(n) = 2n2+5 = 2(1)2+5 = 7
g(n) = 7(n) = 7(1) = 7
Here, f(n)=g(n)
Let n = 2, then
f(n) = 2n2+5 = 2(2)2+5 = 13
g(n) = 7(n) = 7(2) = 14
Here, f(n)<g(n)
Thus, for n=1, we get f(n) ≥ c∗ g(n). This concludes that Omega helps to
determine the "lower bound" of the algorithm's run-time.
Theta Notation

'θ' is the representation for Theta notation. Theta notation is used when the upper bound and lower
bound of an algorithm are in the same order of magnitude. Theta can be defined as:

c 1 ∗ g(n)≤ f(n) ≤ c 2 ∗ g(n) for all n>n 0
Where, n is any number of inputs or outputs and f(n) and g(n) are two non-negative functions. These
functions are true only if there are two constants namely, c1, c2, and a non-negative integer n 0.
Theta can also be denoted as f(n) = θ(g(n)) where, f of n is equal to Theta of g of n. The graphical
representation of f(n) = θ(g(n)) is shown in figure 2.3. The function f(n) is said to be in θ (g(n)) if f(n) is
bounded both above and below by some positive constant multiples of g(n) for all large values of n, i.e.,
if there exists some positive constant c1 and c2 and some non-negative integer n 0, such that
C 2g(n)≤f(n)≤ C 1g(n) for all n≥n 0.

LOVELY PROFESSIONAL UNIVERSITY 23