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.

  • 2
    This is probably not the right place for a pure Big-O question. Maybe try here: cs.stackexchange.com – FrustratedWithFormsDesigner Apr 5 '17 at 19:07
  • Thank you. I saw other complexity problems being answered here and thought it would be okay. – user3026388 Apr 5 '17 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? – FrustratedWithFormsDesigner Apr 5 '17 at 19:09
  • 1
    Possible duplicate of What is O(...) and how do I calculate it? – gnat Apr 5 '17 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. – user3026388 Apr 5 '17 at 19:33

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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.