What is the complexity of this recursive algorithm?

Question

Does the following algorithm have a complexity of O(nlogn)?

The thing that confuses me is that this algorithm divides twice, not once as a regular O(nlogn) algorithm, and each time it does O(n) work.

def equivalent(a, b):

    if isEqual(a, b):
        return True

    half = int(len(a) / 2)
    if 2*half != len(a):
        return False

    if (equivalent(a[:half], b[:half]) and equivalent(a[half:], b[half:])):
        return True

    if (equivalent(a[:half], b[half:]) and equivalent(a[half:], b[:half])):
        return True

    return False

Answer 1

To enhance the above answer, there is a direct way to calculate with 'Master Method'. The master method works only for following type of recurrences.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

We have three cases based on the f(n) as below and reduction for them:

1. If f(n) = Θ(n^c) where c < Log_ba then T(n) = Θ(n ^Log_ba)

2. If f(n) = Θ(n^c) where c = Log_ba then T(n) = Θ(n^c Log n)

3. If f(n) = Θ(n^c) where c > Log_ba then T(n) = Θ(f(n)) = Θ(n^c)

In your case,

we have a = 4, b = 2, c = 1 and c < Log_ba

i.e. 1 < log₂4

Hence => case 1

Therefore: T(n) = Θ(n^Log_ba)

T(n) = Θ(n^Log₂4)

T(n) = Θ(n²)

More details with examples can be found in wiki.

Hope it helps!

Answer 2

Each of the 4 recursive calls to equivalent reduces the amount of input data by a factor of 2. Thus, assuming that a and b have the same length, and isEqual has linear time complexity, we can construct the recurrence relation for the overall complexity:

Where C is some constant. We can solve this relation by repeatedly substituting and spotting a pattern:

What is the upper limit of the summation, m? The stopping condition occurs when len(a) is odd. That may be anywhere between N and 1, depending on the prime decomposition of N. In the worse case scenario, N is a power of 2, so the function recurses until len(a) = 1, i.e.