Time complexity of a recursive algorithm which split into two per run mostly

Question

Dynamic Programming | Set 33 (Find if a string is interleaved of two other strings)

http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/

I found a question in this website and it said "The worst case time complexity of recursive solution is O(2^n).". Therefore, I tried to draw a tree diagram about the worst case this question. I assume that when the length and value of a and b are the same, it will lead to a worst case. It will split into 2 parts till the length of a/b is 0 (using substring).

                    aa,aa,aaaa
                   /          \
                  /            \ 
           a,aa,aaa             aa,a,aaa
          /        \           /        \
         /          \         /          \
     -,aa,aa     a,a,aa     a,a,aa     aa,-,aa
    /           /    |        |   \           \
   /           /     |        |    \           \
-,a,a       -,a,a  a,-,a   -,a,a  a,-,a      a,-,a

In this case, it has 13 nodes which is really a worst case, but how to calculate it step by step? IF the length of c increases by 2, it will got 49 nodes. If it increases to a large number, it will be difficult to draw a tree diagram.

Can someone explain this in details, please?

Merge Sort : i guess this algorithm is using the same idea(spliting into 2 parts utill one element is remaining) . it just didnt group them back. I will say the complexity would be O(n log n) for worst case — brotherofninth
– brotherofninth, Commented Nov 30, 2015 at 16:53

pgpb.padilla · Accepted Answer · 2015-12-03 16:38:14Z

1

The recurrence for the running time is

T(n) = 2T(n-1)

If you draw the recursion tree you'll see that you have a binary tree with height = n.

Since it is a binary tree, it will have 2^n leaves hence the worst case scenario is O(2^n).

answered Dec 3, 2015 at 16:38

pgpb.padilla

2,4362 gold badges21 silver badges47 bronze badges

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

Collectives™ on Stack Overflow

Time complexity of a recursive algorithm which split into two per run mostly

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related