-4

I am having trouble calculating the complexity of this problem:

REVERSE3(A): // Reverse the order of elements in an array
// P is an array; assume generating next permutation takes 1 step.


    for every possible permutation P of A:
      for index i = 1 to N:
        if P[i] is not equal to A[N-i+1]:
          continue to the next permutation
          // All elements matched in proper places
    return P

I think some of my misunderstandings arise from the first for-loop. What does it even mean? How would you calculate the complexity for this?

Any help would be appreciated. Thank you.

Improve this question
5
  • 2
    This is probably not the right place for a pure Big-O question. Maybe try here: cs.stackexchange.com Commented Apr 5, 2017 at 19:07
  • Thank you. I saw other complexity problems being answered here and thought it would be okay. Commented Apr 5, 2017 at 19:08
  • Oh, other complexity problems are answered here? Ok, that might be my mistake, I didn't realize those were on-topic now for this forum. I think at one point they were not, maybe? Commented Apr 5, 2017 at 19:09
  • 1
    Possible duplicate of What is O(...) and how do I calculate it? Commented Apr 5, 2017 at 19:27
  • @gnat This is a lot more specific, indicating I'm having trouble evaluating a certain problem even though I'm familiar with the general steps. Commented Apr 5, 2017 at 19:33

1 Answer 1

Reset to default
0

for every possible permutation P of A:

This is apparently a sort of a joke problem, as this would be almost the most inefficient way possible to sort an array. They want you to step through every possible ordering of the array looking for the one that's sorted correctly.

How many ways can you order an array with M elements? Well, you have M choices for the first position, M - 1 choices for the 2nd position, etc. Does that remind you of a common mathematical function?

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.