analyzing time complexity of a recursive algorithm

Question

I'm learning how to calculate time complexity of an algorithm. I am able to calculate time complexity of a simple algorithm that includes loops , but I'm having trouble calculating time complexity of algorithms that uses recursion. I need help in determining time complexity of recursive algorithm.

The problem statement is as follows:

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#" Output: true Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c" Output: true Explanation: Both S and T become "c".

And the algorithm I have developed is as follows :

 public boolean backspaceCompare(String S, String T) {
      return removeAndDelete(S).equals(removeAndDelete(T));
    }


public  String removeAndDelete(String input){
    int index = input.indexOf('#');
    if(index==-1)
        return input;
    else if(index == 0)
        return removeAndDelete(input.substring(index+1));
    else
        return removeAndDelete(input.substring(0,index-1)+input.substring(index+1));
}

Now I would like to calculate time complexity of my algorithm. Please help me...

user9254539 · Accepted Answer · 2020-04-09 23:07:59Z

3

The complexity is quadratic. Let N be the length of the input string. The number of recursive calls is equal to the number of # characters in the input, which is O(N). Each time you make a recursive call the substring operations take O(N), so we have an upper bound of O(N^2). With an input like aaaa#### it's easy to see that the complexity is at least O(N^2),

answered Apr 9, 2020 at 23:07

user9254539

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

1 Comment

Rohit Over a year ago

Thanks for the explanation.. Now I understand

Collectives™ on Stack Overflow

analyzing time complexity of a recursive algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related