Question

Analysing Asymptotic Bounds (Marks: 3)

Prove the following using the definition of asymptotic order notation.

Example: 15n 3 + 10n 2 + 20 ∈ O(n³ )

Hint: Consider C = 15 + 10 + 20 = 45 and n0 := 1. Then 0 ≤ 12n ³ + 11n ² + 10 ≤ Cn³ for all n ≥ n0.

a) n ² + 3n ² /(2+cos(n)) ∈ O(n ² )

b) 2n ² (log n) ∈ Ω(n(log n) ² )

c) 10n ²/(n − 10) ∈ Θ(n)

Answer 1

a) T(n) = n ² + 3n ² /(2+cos(n))

Consider maximum possible value of T(n)

n ² + 3n ² /(2+cos(n)) <= n ² + 3n ² /(2) <= 2.5 n²

So for C = 2.5 and n0 = 1

0 <= n ² + 3n ² /(2+cos(n)) <= Cn² for all n>= n0

Hence T(n) =O(n²)

=========================

b)

T(n) = 2n ² (log n)

We know that n>=logn for all n>=1

Multiplying both side by 2nlogn

2n ² (log n) >= 2n(log n) ² >=0 for all n>=1

Hence for C =2 and n0 = 1 we have

2n ² (log n) >= 2n(log n) ² >=0 for all n>=1

Hence T(n) =  Ω(n(log n) ² )

===============================

c)

T(n) = 10n ²/(n − 10)

Let n0 = 11, Then

10n ²/(n − 10) >= 10n ²/(n)

10n ²/(n − 10) >= 10 n

Also we have,

10n ²/(n − 10) <= 11 *( 10n ²/n )

Because n-10 >= n/11 for all n>=11

Hence

10n ²/(n − 10) <= 110 n

So we have c1 = 10 and c2 = 110 such that

10n <= 10n ²/(n − 10) <= 110n for all n>= n0 where n0 = 11

Hence T(n) =  Θ(n)

=========================

Please upvote.