l is a matrix of size [1...n, 1...n]
function: rec(i,j)
if (i*j == 0)
return 1
else
if (l[i,j] == 0)
l[i,j] = 1 * rec(i-1,j) + 2 * rec(i,j-1) + 3 * rec(i-1,j-1)
return l[i,j]
end_function
for i=1 to n
for j=1 to n
l[i,j] = 0
rec(n,n)
The nested for's are O(n2). But i have difficulties to analyse the recursive part. There is another variation of this example with l as 3d. And the essential part of 3drec function is defined as:
if (l[i,j,k] == 0)
l[i,j,k] = 2 * rec(i-1,j,k) + 2 * rec(i,j-1,k) + 2 * rec(i,j,k-1)
Anyway let's think about the 2d version again. I thought something like that (that's the running time for the whole code including the nested loops):
T(n) = T(n-1, n2) + T(n, n-12) + T(n-12, n-12)
And i'm stuck here. Besides i don't know if i did right till this point.