# Finding if an array is ordered

I recently wrote a quick code to find if a numeric array is ordered i.e sorted in a ascending or descending order. I needed it to check a sort algorithm I had written. The problem is that the following code has a worst-case running time of O(N). Can we make the running time logarithmic.

 ```/* orderedArray.php */   define("ORDER_ASC", 1); define("ORDER_DSC", 0);   function is_array_ordered(\$array, \$sort_order) { \$i=0; \$total_elements = count(\$array);   if(\$sort_order == ORDER_ASC) { //Check for ascending order while(\$total_elements > 1) { if(\$array[\$i] < \$array[\$i+1]) { \$i++; \$total_elements--; } else { return false; } } } elseif(\$sort_order == ORDER_DSC) { //Check for descending order while(\$total_elements > 1) { if(\$array[\$i] > \$array[\$i+1]) { \$i++; \$total_elements--; } else { return false; } } }   return true; }```

The unit test for the same is given below.

 ```include 'PHPUnit/Framework.php'; include 'orderedArray.php';   class ArrayTest extends PHPUnit_Framework_TestCase { public function testArrayOrder() { // Ascending \$test_array = array(0,1,2,3,4,6,7,8,9,10); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), true);   \$test_array = array(10,9,8,7,6,5,4,3,2,1,0); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), false);   \$test_array = array(0,1,2,3,4,6,7,8,9,10,1); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), false);   \$test_array = array(1,0,1,2,3,4,6,7,8,9,10); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), false);     // Descending \$test_array = array(10,9,8,7,6,5,4,3,2,1,0); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), true);   \$test_array = array(0,1,2,3,4,6,7,8,9,10); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), false);   \$test_array = array(10,9,8,7,6,5,4,3,2,1,0,1); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), false);   \$test_array = array(1,10,9,8,7,6,5,4,3,2,1,0); \$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), false);   } }```

## 2 thoughts on “Finding if an array is ordered”

1. Xr says:

You can’t make the time O(log N) since you have to check every element, which is precisely O(N).

Usually, a logarithmic time means O(N log N), which is worse than O(N) but much better than O(N²). For example, the best sorting algorithms have O(N log N) times (Quicksort with possible degeneration, Heap Sort), while naive ones have O(N²) times.