What is wrong with this P argument

Question

I and my friend made this argument and asked us what could be wrong with it.

Consider an array named “A” with ‘n’ distinct numbers, since A has n! Permutations as you must know that we can’t go through each permutation and check the sorting, and the total time is polynomial in n, therefore, we cannot sorting the array ‘A’ in P.

My other friend thinks that it should sort that array in P. We are confused, kindly guide us...

Answer 1

The problem stated is not clear and not specifying the exact problem

Sorting can be performed using linear-time(O(n)) on the number of elements to be sorted. In case if you are sorting a large list of numbers drawn from a small pool.

Like if you are using linearithmic-time(O(nlogn)) method on the elements which have to be sorted then you are sorting arbitrary things in a list which are totally ordered based on some ordering relations, for example, greater than or equal to.

Sorting performed by partial order for example topological sorting should be analyzed in another way: 

Imagine a sorting problem were the elements are sorted by using sortedness of a list, this can't be determined by comparing adjacent elements alone. In the worst case, sortedness can only be checked by verifying the entire list. If your sorting is designed to guarantee that there is exactly one sorted permutation of any given list then the time complexity will be O(n!), so the problem is not in P.

This is the real problem with the argument in the question mentioned, if your friend is assuming that the sorting refers to an integer, not on a range, then the problem means that we don’t have to consider all the permutations in order to sort. Say, for instance, if you have a bag with 100 apples and when your friend asks you to eliminate 3 apples, the time complexity will be constant-time, it doesn’t matter that there are n(n-1)n-2)/6=161700, or O(n^3) ways you can complete this task.

If you like to learn more about data science and improve your skills, then you can learn online Data Science Courses.