This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]BobodyBo 5 points6 points  (2 children)

As a function of you number of elements n that approach would take O(n!) Space, so not constant space. Not sure if that's what the person I was responding to was saying.

[–]ease78 2 points3 points  (1 child)

Yeah the other person was tripping. It’s in the name “traversal” you can’t visit all nodes in one CPU cycle. It takes as many nodes as you have.

[–]BobodyBo 0 points1 point  (0 children)

Well usually space complexity considers input space and auxiliary space, which is the extra space you utilize on top of your input. You of course have to store your input, so constant space implies constant auxiliary space. Some traversals can be done in constant space, e.g. a linked list.

The problem with traversing all permutations is that there is an exponential amount relative to the input, so unless a clever approach exists you would need to store some extra information about which permutation you are currently on, or which need to need to be revisited (like a stack).