I write this code in python:
def sub(ma):
n = len(ma); m = len(ma[0])
if n != m : return
n2 = int(ceil(n/2))
a = []; b = []; c = []; d = []
for i in range(n2):
a.append(ma[i][0:n2])
b.append(ma[i][n2:n])
c.append(ma[n2+i][0:n2])
d.append(ma[n2+i][n2:n])
return [a,b,c,d]
def sum(ma):
if len(ma) == 1 : return ma[0][0]
div = sub(ma)
return sum(div[0])+sum(div[1])+sum(div[2])+sum(div[3])
Do you know what is a possibly recurrence equation $T(n)$ to the 'sum' method? I suppose that is like that $$T(n) = 4T(n/2) + f(n)$$ what it is $f(n)$ ? Thanks,