edited tags
Raphael
• 70.4k
• 27
• 162
• 359

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

Removed some confusing texts

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

$$1 - T_1(n) = \sqrt{n} T_1(\sqrt{n}) + 3 n, \quad T_1(1) = T_1(2) = 1.$$$$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

$$2 - T_2(n) = 3 T_2(n/3) + 2n \log n, \quad T_2(1) = T_2(2) = 1.$$$$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?

added 186 characters in body; edited title
Yuval Filmus
• 260.5k
• 25
• 276
• 457

# Two recurrance function complexity comparison Comparing two recurrence relations

I have two function T(n), howfunctions $$T_1(n),T_2(n)$$. How do i compareI decide which areis asymptotically betterfaster?

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


One is given by the recurrence relation

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

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


The other is given by the recurrence relation

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

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

For the second one, the Master's theorem is usableapplicable, but as I assume the complexity becomes O(n*nlogn) <==> O(n^2 * logn) => O(n)$$O(n \cdot n \log n) \Leftrightarrow O(n^2 \cdot \log n) \Rightarrow O(n)$$ for loop, aand O(nlogn)$$O(n\log n)$$ for c$$c$$.

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

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


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

Was there some mistakesany mistake, or this is this not how recurrancerecurrence unrolling is being done?