Jump to content

Time and Space Complexity of itertools.permuations


Qubit
 Share

Recommended Posts

Need to know this for a project where we find if a word is a permutation of a another word in a shitty way.. from eye balling it the time complexity to create it is O(n) and the space complexity would be O(n!) too right?

 

 

My program just creates the list via itertools.permutations of the first string, then uses a for loop to go through it and see if it is there...

 

https://docs.python.org/2/library/itertools.html#itertools.permutations

Edited by Qubit
Link to comment
Share on other sites

Need to know this for a project where we find if a word is a permutation of a another word in a shitty way.. from eye balling it the time complexity to create it is O(n!) and the space complexity would be O(n!) too right?

My program just creates the list via itertools.permutations of the first string, then uses a for loop to go through it and see if it is there...

https://docs.python.org/2/library/itertools.html#itertools.permutations

Do you have to do it that way? It seems very inefficient

Link to comment
Share on other sites

Why would you expect the devs to know a permutation shortcut, its specialized knowledge that isn't useful in developing the client. Google it, if you can't find a better way than O(n!) time then its probably not out there.

 

As for using big o notation and time complexity I can't really see the point of using the notation other than showing off or to ask for homework with your CS classes.

Edited by Gary_Oak
Link to comment
Share on other sites

Why would you expect the devs to know a permutation shortcut, its specialized knowledge that isn't useful in developing the client. Google it, if you can't find a better way than O(n!) time then its probably not out there.

As for using big o notation and time complexity I can't really see the point of using the notation other than showing off or to ask for homework with your CS classes.

OP is asking if the time and space complexities he stated are correct, not for a 'shortcut'.

Also big O notation is very useful as it is a high level way of expressing the efficiency of an algorithm, allowing you to see how it will scale and compare it with other algorithms. It isn't for showing off or just for homework...

  • Like 1
Link to comment
Share on other sites

Why would you expect the devs to know a permutation shortcut, its specialized knowledge that isn't useful in developing the client. Google it, if you can't find a better way than O(n!) time then its probably not out there.

 

As for using big o notation and time complexity I can't really see the point of using the notation other than showing off or to ask for homework with your CS classes.

If you took the time to read the two sentences this post is comprised of, you would understand my problem.

 

1. Im not asking for a shortcut, im asking for the time and space complexities. I have already written a algorithm that solves the problem in 2*n => O(n) complexity.

 

2. Algorithms and their complexities are important to know and very much applied. I know for a fact anyone with a brain and especially people who develop the bot client would have some knowledge in the area.

 

3. The notation let's you know the upper bound of an algorithm to know the worst case of the algorithm, which is extremely important to know and many cases. 

 

4.  I literally say this is for a project.. => school " CS class"

Link to comment
Share on other sites

OP is asking if the time and space complexities he stated are correct, not for a 'shortcut'.

Also big O notation is very useful as it is a high level way of expressing the efficiency of an algorithm, allowing you to see how it will scale and compare it with other algorithms. It isn't for showing off or just for homework...

 

I don't disagree but the nature of the question is really buzz wordy and easily answered by google. That python implementation is definitely n!, and a simple google search will answer his question. 

 

That said his question really reeks of trying to show off his knowledge of 200 level CS courses with a non question.

If you took the time to read the two sentences this post is comprised of, you would understand my problem.

 

1. Im not asking for a shortcut, im asking for the time and space complexities. I have already written a algorithm that solves the problem in 2*n => O(n) complexity.

 

2. Algorithms and their complexities are important to know and very much applied. I know for a fact anyone with a brain and especially people who develop the bot client would have some knowledge in the area.

 

3. The notation let's you know the upper bound of an algorithm to know the worst case of the algorithm, which is extremely important to know and many cases. 

 

4.  I literally say this is for a project.. => school " CS class"

 

1. Ask google, its literally the first result. And thats cool that you read your algorithms textbook and read up on radix sort.  And yes anyone who knows the word time complexity  is aware of what you just said and is not impressed by it. 

 

We know that nested for loops are worse than a tree.

Edited by Gary_Oak
  • Like 1
Link to comment
Share on other sites

I don't disagree but the nature of the question is really buzz wordy and easily answered by google. That python implementation is definitely n!, and a simple google search will answer his question. 

 

That said his question really reeks of trying to show off his knowledge of 200 level CS courses with a non question.

 

1. Ask google, its literally the first result. And thats cool that you read your algorithms textbook and read up on radix sort.  And yes anyone who knows the word time complexity  is aware of what you just said and is not impressed by it. 

 

We know that nested for loops are worse than a tree.

 

 

Bruh what you smoking fam? If you click the link of the first google result, it provides a wrong answer to the time complexity and no space complexity answer. Also, what else are you going on about over there? Sounds like you googled algorithms and tried making a horrible comeback response to me after I shat all over your initial reply. 

 

This boy out here smoking penises. Use the word complexity and  some how I am showing off with my buzz words.  

Edited by Qubit
Link to comment
Share on other sites

Need to know this for a project where we find if a word is a permutation of a another word in a shitty way.. from eye balling it the time complexity to create it is O(n) and the space complexity would be O(n!) too right?

My program just creates the list via itertools.permutations of the first string, then uses a for loop to go through it and see if it is there...

https://docs.python.org/2/library/itertools.html#itertools.permutations

I think that the space complexity is O(n) because the method returns a generator, essentially meaning that it generates each value on request. The only thing stored is the input which is O(n)

Regarding time complexity, I would assume that it is O(n!) to generate all of the permutations.

Edited by Explv
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...