Asymptotic Complexity Given two functions f,g : R+ 7R, 1. f O(g(n)) if and only

Question

Asymptotic Complexity

Given two functions

f,g : R+ 7R, 1. f O(g(n)) if and only if c R+,n0 R0(n n0 (f(n) c·g(n))).

2. f (g(n)) if and only if c R+,n0 R0(n n0 (f(n) c·g(n))).

3. f (g(n)) if and only if O(g(n)) and (g(n)).

1. Give derivations that prove the following. For convenience, you may assume that the logarithms are in the base of your choice, but you should specify what base you are using in your derivation.

(a) (n8)2 (n2).

(b) 7n4 5n3 logn6n2 + 9nlogn13n (n4).

(c) 2log(3n3 n2 + 43) O(logn).

Explanation / Answer

Answer 1:

a) (n- 8)^2 = theta(n^2)

Here f(n) = (n - 8)^2 , g(n) = n^2

We know the definition of big theta as :

f(n) = theta(g(n)) iff

c1*g(n) < = f(n) < = c2*g(n) -------------> (1)

Let us take the first part : c1*g(n) < = f(n)

Here c1 = constant , f(n) = ( n - 8)^2 , g(n) = n^2

Now let c1 = 1 , n = 2, therefore

c1*g(n) < = f(n) = 1*(2)^2 < = (2-8)^2  

=> 4 < = 36 true ( at c1 = 1 , n = 2)

Now we proved first part to be true

Now second part : f(n) < = c2*g(n)

c2 = constant = 10 , n = 8

( 8 - 8)^2 < = 10* (8)^2

0 < 640 true ( c1 = 10 , n = 8)

thus both the parts are true . Hence (n - 8)^2 is theta(n^2)

(b) 7n4 5n3 logn6n2 + 9nlogn13n (n4).

Here f(n) =  7n4 5n3 logn6n2 + 9nlogn13n, g(n) = n^4

We know the definition of big Omega :

f(n) = Omega(g(n)) iff :

f(n) > = c*g(n)

7n4 5n3 logn6n2 + 9nlogn13n > = c*n^4

let n = 4 , c = 1

7*(4)^4 - 5(4)^3log4 - 6(4)^2 +9(4)log4 - 13(4) > = 1*(4)^4

1792 - 640 - 96 + 72 - 52 > = 256

1792 +72 - 1088 > = 256

1864 - 1088 > = 256

776 > = 256 TRUE at c = 1 , n = 4 . Hence  7n4 5n3 logn6n2 + 9nlogn13n = Omega(n^4)

(c) 2log(3n3 n2 + 43) O(logn).

Here f(n) = 2log(3n3 n2 + 43) , g(n) = logn

by big O definition :

f(n) = O(g(n)) iff :

f(n) < = c*g(n)

2log(3n3 n2 + 43) < = c*logn

Let n = 2 , c = 100

2log(3(2)^3 - (2)^2 + 43 ) < = 100*log2

2log( 63) < = 100

2*5.977 < = 100 true.

Hence 2log(3n3 n2 + 43) = O(logn)

PLEASE RATE IT IF HELPS .

THANK YOU

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.