C

int is_sorted(int *T, int n) { return false; } 

Works with probability 1-(1/n!) and complexity O(1). Obviously the best method for very large random arrays.

As the complexity is only O(1), for a better estimation, run twice.

C

int is_sorted(int *T, int n) { return false; } 

Works with probability 1-(1/n!) and complexity O(1). Obviously the best method for very large random arrays.

As the complexity is only O(1), for a better estimation, run twice.