For each part say whether the statement is true or false and

For each part, say whether the statement is true or false and justify your answer. All logarithms are base 2 unless otherwise noted.

a) 2ⁿ ? ?(4ⁿ)

b) log(n²) + log(10¹⁰n¹⁰) ? O(logn)

d) n / ln(n) ? ?( (ln(n)) ² )

e) If log f(n) ? ?(log g(n)), then f(n) ? ?(g(n)).

Answer:

a) 2ⁿ (4ⁿ)

We know theta definition :

c1.g(n) <= f(n) < = c2.g(n)

c1 x 4^n < = 2^n < = 4^n x c2

Let c1 = 2 and c2 = 4

Now 2 x 4^n < = 2^n

Let n = 1

2 x 4 < = 2^1 => 8 < = 2 , which is wrong

Therefore 2^n is not theta(4^n

b) b) log(n²) + log(10¹⁰n¹⁰) O(logn)

Solution : We know big O definition :

f(n) < = g(n)

log(n^2) + log(10^10 n^10) < = logn

2logn + 10log10 + 10logn <= logn

= 2logn + 10 + 10logn < = logn

So the heighst term is logn in the left , so O(logn) ... True

c) 2^n belongs to O( (2)^n)

Solution : 2^n (2)^n

= > (2^n)^1/2 (2)1/2n

Taking log log[ (2^n)^1/2 ] log[( 2)1/2n ]

=> 1/2 log ( 2^n) 1/2nlog2

=> 1/2n log2 1/2n log2

= > 1/2n = 1/2n

both are equal , and we know the big O , definition

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

Therefore given statement is true

d) n / ln(n) ( (ln(n)) ² )

Solution : we know omega definition :

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

n / ln(n) > = ln(n)^2

n/ln(n) > = 2ln(n)

it is not true if we put values , therefore given statement is false.