aman_naughty's blog

Can someone tell the time complexity of this code?
By aman_naughty, history, 5 years ago, In English

code

I cannot estimate the time complexity of this code? This code is for optimal binary search tree dp problem.

Is it O(n3) or O(n4) or O(n2)

Someone please help.

Also if someone could tell me some tutorial on how to find time complexity of recursion.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's n^4 absolutely.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You have n^3 states and each of them need O(n) transformation

→ Reply