Page 28 - DCAP407_DATA_STRUCTURE

Unit 2: Complexity Analysis

Table 2.1 gives some names and examples of the common orders used to describe functions. These
orders are ranked from top to bottom.

Table 2.1: Common Orders

Time complexity Examples
O(1) Constant Adding to the front of a linked list
O(log n) Logarithmic Finding an entry in a sorted array

O(n) Linear Finding an entry in an unsorted array
O(n log n) Linearithmic Sorting ‘n’ items by ‘divide-and-conquer’
O(n2) Quadratic Shortest path between two nodes in a graph
O(n3) Cubic Simultaneous linear equations
O(2n) Exponential The Towers of Hanoi problem

Big-O notation is generally used to express an ordering property among the functions. This notation
helps in calculating the maximum amount of time taken by an algorithm to compute a problem. Big-O
is defined as:
f(n) ≤ c∗ g(n)

where, n can be any number of inputs or outputs and f(n) as well as 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.
The Big-O can also be denoted as f(n) = O(g(n)), where f(n) and g(n) are two non-negative functions and
f(n) < g(n) if g(n) is multiple of some constant c. The graphical representation of f(n) = O(g(n)) is shown
in figure 2.1, where the running time increases considerably when n increases.

Consider f(n)=15n +40n +2nlog n+2n. As the value of n increases, n becomes
3
2
3
much larger than n , nlog n, and n. Hence, it dominates the function f(n) and we
2
can consider the running time to grow by the order of n . Therefore, it can be
3
written as f(n)=O(n ).
3
The values of n for f(n) and C* g(n) will not be less than n 0. Therefore, the values less than n 0 are not
considered relevant.
Figure 2.1: Big-O Notation f(n) = O(g(n))

Source: Puntambekar, A., A. (2010). Design and Analysis of Algorithms, Technical Publications Pune.

LOVELY PROFESSIONAL UNIVERSITY 21