E SolutionAnswer n nlogn Proof We know the theta definition

Solution

Answer:

n + nlogn

Proof:

We know the theta definition:

c1*g(n) < = f(n) <= c2*g(n) , where c is a constant and is greater than zero

Here f(n) = n +nlogn , g(n) = nlogn

c1* nlogn < = n + nlogn < = c2*nlogn

Let c1 = 2 , c1 = 1

nlogn < = n + nlogn < = nlogn

nlogn < = n + nlogn

check at higher values of n , nlogn will be less than n + nlogn