Given an array, A, of n integers, find the longest subarray of A such that all the numbers in that subarray are in sorted order. What is the running time of your method?

Question

Computers and Technology

Sariah

25 October, 09:27

Given an array, A, of n integers, find the longest subarray of A such that all the numbers in that subarray are in sorted order. What is the running time of your method?

+3

Answers (1)

Know the Answer?

Rebekah · Answer 1

Running time for best case = O (n)

Running time for worst case = O (n^2)

Explanation:

function to find the longest subarray:

int findSortedSubArray (int A[], int n)

{

int i=0, j=0;

int maxLength=1, tempLength=1;

for (i=0; i
{

tempLength=1;

for (j=i; j
{

if (A[j]<=A[j+1] && (j+1) !=n-1)

{

tempLength++;

}

else

{

if (tempLength>maxLength)

{

maxLength=tempLength;

}

break;

}

}

}

return maxLength;

}

Running time for best case:

The loops inside this function are nested for loops. The loop that runs n-1 times is the outer loop and the loop that runs only once is the inner loop. Hence, the number of steps executed by the nested for loops = n-1 = O (n)

Running time for worst case:

The total no. of steps executed = 1+2+ ... n-2+n-1 = ((n-1) (n)) / 2 = (n^2 - n) / 2 = O (n^2)