Time Complexity!

  • 0

    Firstly the recursion tree:
    n options on 1st layer, n - 1 options on 2nd layer ...
    So, the recursion tree has (n!) nodes.

    Then, in every recursion node:
    we did a traverse on original array to check whether we can take the element or not.
    This takes O(n)

    And, every time we check an element:
    We uses List.contains(), this method cost O(n) too.

    So, totally the time complexity should be:
    O(n * n * n!) = O(n^3)

    If we use a boolean array boolean[] used, we can avoid using List.contains() and make this step to O(1), so the total time will be:
    O(n * n!) = O(n^2)

    Are these correct???
    Please comment.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.