HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Computing the running time of a divide-by-4-and-conquer algorithm

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dividethetimealgorithmrunningandconquercomputing

Problem

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,

Solution

The subroutine sub quarters the matrix into four parts. This takes time $f(n)$, and so the running-time of sum (which sums all entries in its input square matrix in a curious divide-and-conquer fashion) satisfies the recurrence
$$ T(n) = \begin{cases} O(1) & n=1 \\ 2T(\lfloor n/2 \rfloor) + 2T(\lceil n/2 \rceil) + f(n) + O(1) & n>1. \end{cases} $$
The subroutine sub is quite simple, and I'm sure you can figure out its running time yourself (though you'll have to be careful about the semantics of list appending in python).

Context

StackExchange Computer Science Q#4584, answer score: 4

Revisions (0)

No revisions yet.