Word Break -II Leetcode

#1

What is Time Complexity of this Code
https://ide.geeksforgeeks.org/rd6WKwZppm

#2

Hey @Bhawna
There is no set time complexity of such questions.
For an upper bound assume this

    for(auto word:st)//(O(n))
    {
        vector<string> temp=wordBreak1(s.substr(word.length()),st); //n times recursive call by subtractinf length of actual string by 1  i.e assumin word.length()=1
        for(string t:temp){//O(n)
         }
    }

So assume T(len)=n*T(len-1) + O(n) So this is just an approximate relationship but actual relationship will be very different from this and since it contains two vars ,I don’t think one can find its time complexity via normal maths :slight_smile:

#3

So,then What to tell in Interview it’s Time Complexity

#4

He will not ask u its time complexity most probably
Though u can look in discussion of that question

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.