Garvit_2013's blog

Confusion about Time Complexity (help)
By Garvit_2013, history, 3 years ago, In English

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://mirror.codeforces.com/contest/1646/submission/148429105

Thanks in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks

    Can you please explain how you arrive at this complexity?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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)$$$

      → Reply