# recurrence relation – Two dimensional recursive function in \$Olog n\$ time complexity

It is well known that a recursive sequence or $$1$$-d sequence can be solved in $$O log n$$ time given that it has the form

$$a_n=sum_{k=1}^{n} C_ka_{n-k}$$

where $$C_k$$ is a constant. Examples would include polynomials like $$n^2$$ or $$n^3$$, exponentials like $$2^n$$, and Fibonacci Numbers defined by $$a_n=a_{n-1}+a_{n-2}, a_0=0, a_1=1$$. Factorials would not be included for example, because they are defined by $$a_n=na_{n-1}$$, and $$C_k=n$$ is not constant.

Let $$a_{n,k}$$ be a two dimensional sequence defined by

$$a_{n,k} = sum_{i=0,j=0, (ine n text{ }âˆ§text{ }jne k)}^{n,k}C_{i,j}a_{i,j}$$

where $$C_{i,j}$$ is constant.

Is it possible to compute $$a_{n,k}$$ in logarithmic time (a.k.a $$O log n$$) or better?

I know one case where this is possible, namely if $$a_{n,k}$$ are coefficients of polynomials in a sequence ($$1$$-d recursive sequence), such that the degrees of each term differ by $$1$$. In this case, the diagonals of the sequence $$a_{n,n+t}$$ for some constant $$t$$, are $$1$$-d constant recursive functions, whose terms can be computed in $$Olog n$$ time. This doesn’t use the initial relation in terms of two indices though as expected.

However, in certain cases, the diagonals do not form $$1$$-d constant recursive functions, namely when the degree difference of consecutive polynomial terms is more than $$1$$.