4 of 4
edited tags
Raphael
• 70.5k
• 27
• 163
• 361

# Comparing two recurrence relations w.r.t. asymptotic growth

I have two functions $$T_1(n),T_2(n)$$. How do I decide which is asymptotically faster?

One is given by the recurrence relation

$$T_1(n) = \sqrt{n} T_1(\sqrt{n}) + 3 n, \quad T_1(1) = T_1(2) = 1.$$

The other is given by the recurrence relation

$$T_2(n) = 3 T_2(n/3) + 2n \log n, \quad T_2(1) = T_2(2) = 1.$$

For the first function I guess there is $$O(\sqrt{n} \cdot \sqrt{n})$$ for loop, and $$O(n)$$ for the $$c$$; which becomes $$O(n^2)$$ in total.

For the second one, the Master's theorem is applicable, but as I assume the complexity becomes $$O(n \cdot n \log n) \Leftrightarrow O(n^2 \cdot \log n) \Rightarrow O(n)$$ for loop, and $$O(n\log n)$$ for $$c$$.

So if I am comparing both $$O()$$'s, we can in total see that

$$O(n^2) < O(n^2 \cdot \log n)$$

Was there any mistake, or is this not how recurrence unrolling is done?