Big O notation true or false questions Are these true or fal

Big O notation true or false questions?

Are these true or false? Please prove using definition of Big-Theta. Clearly state what c and n0 you choose for the True answer (these constants do not have to be the same for big-O and big-Theta) or explain why such constants can not be chosen.

Solution

Answer:

11. n^2 + n ! = theta(n^n )

Here f(n) = n^2 + n! , g(n ) = n^n

We knw theta notation :

c1 * g(n) < = f(n) < c2 x g(n)

Now lets us c1 * g(n) < = f(n)

c1* n^n < n^2 + n!

Let c1 = 1 , n = 2

1 * 2^2 < = 2^2 + 2

4 < = 6 ( satisfied the theta notation at n = 2 and c1 = 1

Now lets check f(n) < = c2 * g(n)

n^2 + n! < = n^n * c2

let n = 1 , c2 = 2

1 + 1 < = 1 *2

Thus the given equation is true .

12. 100n^2 + n = theta(n^2)

We know theta definition

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

c1* n^2 < = 100n^2 + n < = c2* n^2

Lets take c1* n^2 < = 100n^2 + n

let c1 = 1 , n = 1

1 * 1 < 100(1)^2 + 1

satisfies at c1 = 1 and n = 1

now take another part f(n) < = c2*g(n)

100n^2 + n < = c1*n^2

let c = 100 , n = 1

100 + 1 < = 100

Satisfies at c = 100 , n = 1

Therefore it is true

13.

n + root (n) = theta(n)

It is true because the hieghst term is n.

14 n * 1/n + log8

= 1 + log8

It is theta(1) , because it is independent of n

15 . n + logn^n = theta ( nlogn)

Here n + nlogn^n = n + nlogn , hieghst term is nlogn , therefore theta(nlogn) , true.