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

meowgoesthedog · Accepted Answer · 2017-08-17 23:28:52Z

7

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.

answered Aug 17, 2017 at 23:28

meowgoesthedog

15.1k4 gold badges30 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ayman Over a year ago

Thanks, that helped me a lot, could you give me a reference to learn how to find the comlexity

meowgoesthedog Over a year ago

@ayman for recursive functions the first step is always to find the recurrence relation. Once you have that you can make a range of different substitutions. If the relation is of the form T(n) = aT(n/b) + f(n), which is surprisingly common, then you can use the master theorem.

arunk2 · Accepted Answer · 2017-08-28 06:32:47Z

2

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:

If f(n) = Θ(n^c) where c < Log_ba then T(n) = Θ(n ^Log_ba)
If f(n) = Θ(n^c) where c = Log_ba then T(n) = Θ(n^c Log n)
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!

edited Aug 28, 2017 at 6:32

answered Aug 19, 2017 at 7:10

arunk2

2,4563 gold badges25 silver badges35 bronze badges

Collectives™ on Stack Overflow

What is the complexity of this recursive algorithm?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related