Need help in determining the time complexity of a function

Revision en1, by xeno3112, 2020-05-24 22:54:22

This is the function I used for solving “removing duplicate elements from a string”. I am unable to figure out its time complexity. What is its time complexity? https://practice.geeksforgeeks.org/problems/recursively-remove-all-adjacent-duplicates/0

inline string removedup(string s){
    int n = s.length();
    if(n == 1)
        return s;
    int i = 1;
    string str;
    if(s[0] != s[1])
        str.push_back(s[0]);
    while(i < n){
        if(s[i] == s[i - 1]);
        else if(i < n-1 and s[i] == s[i+1]);
        else
            str.push_back(s[i]);
        i++;
    }
    if(str.length() == 0)
        return str;
    if(str.length() != n)
        return removedup(str);
    return str;
}
Tags #running time, time complexity, c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English xeno3112 2020-05-24 22:54:22 816 Initial revision (published)