Time and Space Complexity of itertools.permuations

[Qubit]

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 November 26, 2016 by Qubit

[Rxd]

You think anyone here is smart enough to answer these?

[Qubit]

You think anyone here is smart enough to answer these?

 

Ehh.. there's a couple scriptersand I would expect the devs too

[Explv]

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

[Gary_Oak]

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 November 26, 2016 by Gary_Oak

[Qubit]

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

Yea its part of the project... I had to make another one that was O(n) that was simple.

[Explv]

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...

[Qubit]

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"

[Gary_Oak]

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 November 26, 2016 by Gary_Oak

[Ducky]

[Qubit]

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 November 26, 2016 by Qubit

[Explv]

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 November 26, 2016 by Explv

[Easy]

Yea its part of the project... I had to make another one that was O(n) that was simple.

Not as hard as finding the matrixes for world to screen xd

Edited November 28, 2016 by Flamo