TransWikia.com

How to solve recursion with two separate converges rates

Computer Science Asked by Ofir Gordon on December 10, 2021

What is the correct way to solve the following recursion:
$T(n)=T(lceilfrac{n}{2}rceil) + T(n-2)$

Or basically any recursion that has two parts which converge in a different rate.

I’m trying to get big $O$ approximation, as tight as possible, but I couldn’t figure it out with any "traditional" approach.

One Answer

If you take the initial conditions $T(0) = 0$ and $T(1) = 1$ then you get A018819 (up to shift), which is essentially A000123. The asymptotics are known to be $T(n) = n^{Theta(log n)}$. The references under the second entry contain more accurate asymptotic information.

More explicitly, A018819 satisfies the recurrence $a(2m+1) = a(2m) = a(2m-1) + a(m)$, with $a(0) = a(1) = 1$. You can show inductively that $a(n) = T(n+1)$. Indeed:

  • If $n = 2m+1$ then $$T(n+1) = T(2m+2) = T(m+1) + T(2m) = a(m) + a(2m-1) = a(2m) = a(2m+1) = a(n).$$
  • If $n = 2m$ then $$T(n+1) = T(2m+1) = T(m+1) + T(2m-1) = a(m) + a(2m-2) = a(m) + a(2m-1) = a(2m) = a(n).$$

Answered by Yuval Filmus on December 10, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP