- #1
Constantinos
- 83
- 1
Hey!
I was trying to find the expected time an algorithm takes to solve a certain problem, and I ended up in a very nasty recurrence relation of this form:
a[itex]_{k,k}[/itex] = [itex]\overline{c}[/itex]a[itex]_{k,k-1}[/itex]+[itex]\overline{c}[/itex]a[itex]_{k-1,k}[/itex]+c[itex]^{2}[/itex]a[itex]_{k-1,k-1}[/itex]-[itex]\overline{c}[/itex][itex]^{3}[/itex]a[itex]_{k-1,k-2}[/itex]-[itex]\overline{c}[/itex][itex]^{3}[/itex]a[itex]_{k-2,k-1}[/itex]+([itex]\overline{c}[/itex]-c)[itex]\overline{c}[/itex][itex]^{2}[/itex]a[itex]_{k-2,k-2}[/itex]+y((k,k))
with initial conditions:
a[itex]_{n,0}[/itex] = n [itex]\forall[/itex] n
and
a[itex]_{0,n}[/itex] = n [itex]\forall[/itex] n
and a,y:[itex]N[/itex]X[itex]N[/itex]→ℝ
I have no idea where to even begin! I've never encountered such a thing before, and it is actually a simpler version of a relation involving the full history of the recurrence relation(i.e all of the terms a[itex]_{k1,k2}[/itex] : k1≤k, k2≤ k )
What methods do I have to study to solve that?
I was trying to find the expected time an algorithm takes to solve a certain problem, and I ended up in a very nasty recurrence relation of this form:
a[itex]_{k,k}[/itex] = [itex]\overline{c}[/itex]a[itex]_{k,k-1}[/itex]+[itex]\overline{c}[/itex]a[itex]_{k-1,k}[/itex]+c[itex]^{2}[/itex]a[itex]_{k-1,k-1}[/itex]-[itex]\overline{c}[/itex][itex]^{3}[/itex]a[itex]_{k-1,k-2}[/itex]-[itex]\overline{c}[/itex][itex]^{3}[/itex]a[itex]_{k-2,k-1}[/itex]+([itex]\overline{c}[/itex]-c)[itex]\overline{c}[/itex][itex]^{2}[/itex]a[itex]_{k-2,k-2}[/itex]+y((k,k))
with initial conditions:
a[itex]_{n,0}[/itex] = n [itex]\forall[/itex] n
and
a[itex]_{0,n}[/itex] = n [itex]\forall[/itex] n
and a,y:[itex]N[/itex]X[itex]N[/itex]→ℝ
I have no idea where to even begin! I've never encountered such a thing before, and it is actually a simpler version of a relation involving the full history of the recurrence relation(i.e all of the terms a[itex]_{k1,k2}[/itex] : k1≤k, k2≤ k )
What methods do I have to study to solve that?