Question

***Please answer all the following (Computer science) Discrete math question completely.***

Q2. Growth of functions. In each of the following cases, either construct a function /(/n) that satisfies the specified constraints or state that no such function exists. (2pt each) b, (n)-Ω(n2) and/(n)-O (n + n') In the following two questions, arrange the functions in a list so that each function is a big-O of the next function. (2pt each) d. nlog n, V', log n, (log2n+log n+n), 12 n, (n!), log log() e. 2"+1 n, (n-

Answer 1

Solution:

The first question have been answered as per Chegg guidelines, please repost others.  

Let's have a look at the definition of Big-O, Big-Omega, and Theta first.

Ta リ 干 ames ationi

1 2. 2. l o U B

a)

In this case, both are of Theta notation, this means that no such function exists.

b)

In this case if the function f(n) = n^2

then we can say

f(n) = $\Omega$(n^2)

because

n^2> = c * n^2

for c>0

and also f(n)= O(n^2 + n^3)

in this case

n^2< = c * (n^2 + n^3)

for c>0

c)

in this case different value of f(n) is possible

which can be from 1 (which means constant) to n^50

suppose f(n) = (n^50)

then in case f(n) = O(50)

n^50<= c*n^50

the inequality holds true for c

and also

n^50<= c*2^n

for c>0

the inequality holds true for c

d)

$log\ log\ (n^3)=O(log^3\ n)= O(\sqrt{n^3})=O((n^2 + log^2\ n))= O(n^2/ log\ n)=O(12\ n^5)$

e)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)