Given that rn nlogn and tn n125 which grows faster Prove i

Given that r(n) = nlogn and t(n) = n^1.25, which grows faster? Prove it with the Limit Method in computer science.

Given that r(n) nlogn and t n) ni which grows faster? Prove it. 1.25

Solution

r(n) = nlogn and t(n) = n^1.25

We can rewrite t(n) = n* n^.25

now if we take n^.25 =z, we have to compare between logn and n^.25

take large value of n say = 2^400.

so log n => log 2^400 => 400. (taking log base 2)

and n^.25 => 2^400*(.25) => 2^100 So, n^.25 > logn .

Hence n * n^.25 > n* logn

So, n*n^.25 grows faster than n logn.