Блог пользователя aman_naughty

Can someone tell the time complexity of this code?
Автор aman_naughty, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's n^4 absolutely.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить