Page 29 - DCAP407_DATA_STRUCTURE

Data Structure

Let us take an example to understand the Big-O notation more clearly.

Consider function f(n) = 2(n)+2 and g(n) = n .
2
We need to find the constant c such that f(n) ≤ c∗ g(n).
Let n = 1, then
f(n) = 2(n)+2 = 2(1)+2 = 4
g(n) = n = 1 = 1
2
2
Here, f(n)>g(n)
Let n = 2, then
f(n) = 2(n)+2 = 2(2)+2 = 6
g(n) = n = 2 = 4
2
2
Here, f(n)>g(n)
Let n = 3, then
f(n) = 2(n)+2 = 2(3)+2 = 8
g(n) = n = 3 = 9
2
2
Here, f(n)<g(n)
Thus, when n is greater than 2, we get f(n)<g(n). In other words, as n becomes
larger, the running time increases considerably. This concludes that the Big-O
helps to determine the ‘upper bound’ of the algorithm’s run-time.

1. Big-O notation ignores all the constant factors and lower order factors of n.
2. Big-O notation does not determine how quickly or slowly the algorithms

actually execute for a given input.
Omega Notation
‘Ω’ is the representation for Omega notation. Omega describes the manner in which an algorithm
performs in the best case time complexity. This notation provides the minimum amount of time taken
by an algorithm to compute a problem. Thus, it is considered that omega gives the "lower bound" of the
algorithm's run-time. Omega is defined as:
f(n)≥ c∗ g(n)
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 is a constant c and a non-negative integer n 0 such that n>n 0.

Omega can also be denoted as f(n) = Ώ (g(n)) where, f of n is equal to Omega of g of n. The graphical
representation of f(n) = Ώ (g(n)) is shown in figure 2.2. The function f(n) is said to be in Ώ (g(n)), if f(n)
is bounded below by some constant multiple of g(n) for all large values of n, i.e., if there exists some
positive constant c and some non-negative integer n 0, such that f(n) ≥ c∗ g(n) for all n ≥n 0.

22 LOVELY PROFESSIONAL UNIVERSITY