How do I analyse the complexity of this code? Is it nlog(n)?


  • 0
    L
    class Solution {
    public:
        string reverseString(string s) {
            if(s == "") return s;
            if(s.length() == 1) return s;
            string leftStr = s.substr(0,s.length()/2); 
            string rightStr = s.substr(s.length()/2,s.length());
               
            return reverseString(rightStr) + reverseString(leftStr);
            
        }
    };
    

  • 0
    K

    @lekhaemerald I drew the function call of your code and it forms a tree with 2n-1 nodes. Time complexity of traversal of a tree with n nodes is known to be O(n). So yours will be O(2n-1) which means O(n).
    But when I submit your solution, it is really slow than the others. So I am suspicious about my solution, maybe I thought something wrong or maybe it is about substr.
    If a guy with more knowledge about time complexities responds back, it will be good for both of us:)
    (Btw, I am not a C++ coder)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.