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

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

Removed some confusing texts
Source Link

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?

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. $$

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 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?

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?

added 186 characters in body; edited title
Source Link
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?

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;

and

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?

Comparing two recurrence relations

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. $$

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 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?

Source Link
Loading