1 of 4

Two recurrance function complexity comparison

I have two function T(n), how do i compare which are asymptotically better

1 - T(n) = n^(1/2) T(n^(1/2)) + 3 n, T(1) = 1, T(2) = 1;


2 - T(n) = 3 T(n/3) + 2n log n, T(1) = 1, T(2) = 1.

For the first function i guess there is O(sqrt(n)*sqrt(n)) for loop, and O(n) for the c; which becomes O(n^2) totally For the second one, the Master's theorem is usable, but as I assume the complexity becomes O(n*nlogn) <==> O(n^2 * logn) => O(n) for loop, a O(nlogn) for c

So if comparing both O()'s we can totally see that

O(n^2) < O(n^2 * logn)

Was there some mistakes, or this is not how recurrance unrolling is being done?