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

Confusion about Time Complexity (help)
Автор Garvit_2013, история, 2 года назад, По-английски

Can anybody tell me Time complexity of my code? I am confused a lot about this . I think it should be 14! or 14^14 or something else. Please help me and tell me If I am wrong.

Code Link https://codeforces.com/contest/1646/submission/148429105

Thanks in advance

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

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

The time complexity seems to be $$$O(2^f)$$$ where $$$f$$$ is the size of your factorial array.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks

    Can you please explain how you arrive at this complexity?

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

      Oh, I am sorry, I actually made a mistake and the time complexity is actually more like $$$O(f\cdot2^f)$$$.

      When I saw your code, I deduced that your recursive method is actually just recursing over all subsets(which is equal to $$$2^f$$$) and each recursive call also iterates from $$$i..f$$$ branching more recursive calls. Therefore, $$$2^f$$$ recursive calls, and for each call, we iterate at most $$$f$$$ times making our time complexity $$$O(f\cdot2^f)$$$

      If you want a bit more concrete explanation, I can try :), let's denote $$$T(f)$$$ to be the number of operations your recursive method performs for a size $$$f$$$ array. Note that, the $$$T(f)$$$ could be written as $$$T(f)=f+T(f-1)+T(f-2).......$$$.

      Can you see why?

      Now, working some math out $$$T(f)=f+T(f-1)+T(f-2).......\leq f\cdot 2^f$$$ which I will convinentiely skip ;). Hence, our time complexity is $$$O(f\cdot2^f)$$$

      → Ответить