Page 31 - DCAP407_DATA_STRUCTURE

Data Structure

Figure 2.3 shows Theta notation.

Figure 2.3: Theta Notation f(n) = θ(g(n))

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

Consider function f(n) = 4n + 3 and g(n) = 4n for all n≥ 3; and f(n) = 4n + 3 and

g(n) = 5n for all n ≥ 3.
Then the result of the function will be:
Let n = 3
f(n) = 4n + 3 = 4(3)+3 = 15
g(n) = 4n =4(3) = 12 and
f(n) = 4n + 3 = 4(3)+3 = 15
g(n) = 5n =5(3) = 15 and
here, c1 is 4, c2 is 5 and n0 is 3
Thus, from the above equation we get c1 g(n) f(n) c2 g(n). This concludes that
Theta notation depicts the running time between the upper bound and lower
bound.

Determine a constant p for a given function f(n) ≥ c∗ g(n) where f(n)=2n+3 and
g(n)=2n.

2.1.2 Mathematical Functions
Mathematical functions express the idea that an input completely determines an output. A function
provides exactly one value to each input of a specified type. The value can be real numbers or can be
elements from any given sets: the domain and the codomain of the function.

24 LOVELY PROFESSIONAL UNIVERSITY