Question

Growth of functions. Using the definitions of Θ, Ο, and Ω show that:

a. 5 − 2 = Θ( )

b. 2 + 6 = O( )

c. 3 = Ω()

Answer 1

Required definitions -

1. “f(x) is O(g(x))”, if there are positive constants C and k such that

|f(x)| ≤ C |g(x)| for all x>k

2. "f(x) is Ω(g(x))", if there are positive constants C and k such that

|f(x)| ≥ C |g(x)| for all x>k

3. "f(x) is Θ(g(x))", if f(x) is both O(g(x)) and Ω(g(x)).

a. 5 - 2

Find for O(.)

5 - 2 = 3 = f(x)

Take g(x) = 1, C = 4

=> 3 ≤ 4

=> 5 - 2 = O(1)

Find for Ω(.)

Take g(x) = 1, C = 1

=> 3 ≥ 1

=> 5 - 2 = Ω(1)

=> 5 - 2 = Θ(1)

b. 2 + 6

2 + 6 = 8 = f(x)

Take g(x) = 1, C = 8

=> 8 ≤ 8

=> 2 + 6 = O(1)

c. 3

3 = f(x)

Take g(x) = 1, C = 1

=> 3 ≥ 1

=> 3 = Ω(1)