Timeline for Solving or approximating recurrence relations for sequences of numbers
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 19, 2012 at 15:59 | comment | added | JeffE | Actually, it suffices to observe (inductively) that $T(n)/(n+1) = \Theta(t^*(n))$, where $t^*(n) = 1/n + t^*(n-1)$. In fact, I already used that trick at the very start, when I replaced the $\Theta(n)$ time to partition an array with the simpler $n$. This is an utterly standard abuse of notation. | |
| Jul 17, 2012 at 21:48 | comment | added | Raphael | If you want the precise solution for $T$, that's also not hard (here), if a bit tedious; we get $T(n) = 2(n+1)H_n + (T(0) - 3)n + T(0)$. Actually, $\sum_{i=1}^n \Theta(1/i) = \Theta(H_n)$ confuses me so I prefer the precise variant. Pesky sums of Landau terms. | |
| Jul 17, 2012 at 20:14 | history | answered | JeffE | CC BY-SA 3.0 |