Show that 100n lg n50n n log n You have to use the formal d

Show that 100n lg n+50n = (n log n). You have to use the formal denition of (you must and specify c₁, c₂, n₀).

Solution

Answer:

We have given

f(n) = 100nlogn +50n , g(n) = nlogn

We know theta definition

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

let c1 = 1 , c2 = 1000

nlogn < = 100nlogn + 50n < = 1000 *nlogn

Now calculate :

nlogn < = 100nlogn + 50n

nlogn - 100nlogn = 50n

-99nlogn = 50n

-99nlogn -50n = 0

-99logn -50 = 0

-99logn = 50

n = 2

100nlogn +50n < = 1000*nlogn

100nlogn +50n - 1000nlogn = 0

100logn - 1000logn = 50

2logn -20logn = 1

logn(2 -20) = 1

logn * -18 = 1

logn = 1/18

n = e^1/18 = 1.057

Therefore 100nlogn +50 = theta(nlogn) at c1 = 1 , n = 1000 , n = 2