What is the time-Complexity for the following code?

Question

What is the time complexity for this code?

In this code I am trying to solve the "Palindrome Partitioning" problem. I am using recursion. I am trying to understand DP. and through this program I want to analyse it's time complexity. I want to compare it with the bottom-up approach of Dynamic Programming. The bottom-up approach takes O(n^3) and I have problem finding time complexity for recursive functions. Please help

string str;

int l;
int cut[200][200];
bool isPalin(int i,int j)
{
    bool f=true;
    for(int x=i,y=j;x<y;x++,y--)
        if(str[x]!=str[y])f=false;
    return f;
}
int func(int i,int j)
{
  if(i==j){cut[i][j]=0;return 0;}
  if(isPalin(i,j))return 0;
  if(cut[i][j]!=-1)return cut[i][j];
  cut[i][j]=9999999;
  for(int k=i;k<j;k++)
  {
    cut[i][j]=min(cut[i][j],func(i,k)+1+func(k+1,j));
  }
  return cut[i][j];
}
int main()
{
  while(1){
  cin>>str;
  l=str.size();
  for(int i=0;i<l;i++)
    for(int j=0;j<l;j++)
          cut[i][j]=-1;
  cout<<func(0,str.size()-1)<<endl;
 }
 return 0;
}

Your question isn't refined enough. What problem are you having determining the time complexity of this code? What *specifically* do you need help with? (As asked, this question is "Do my work for me.", which isn't a question.) — David Schwartz, Dec 27 '13 at 09:40
@DavidSchwartz : I am trying to understand DP. and through this program I want to analyse it's time complexity. I want to compare it with the bottom-up approach of Dynamic Programming. The bottom-up approach takes O(n^3) and I have problem finding time complexity for recursive functions. Please help. — user3138968, Dec 27 '13 at 10:00
Look at the [2709106](http://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm) question. The answer contains the perfect instructions for understanding the time complexity for recursive functions. — yakov, Dec 27 '13 at 10:20

score 0 · Answer 1 · edited May 23 '17 at 12:19

0

I hope you will make it out by yourself after reading the question 11032015. That topic contains two clear, detailed and complete answers. Good luck.

edited May 23 '17 at 12:19

Community

1
1

answered Dec 27 '13 at 10:07

yakov

444
3
14

What is the time-Complexity for the following code?

1 Answers1