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

Penny

Computers & Technology

26 June, 21:51

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?

+1

Answers (1)

Know the Answer?

Lilia Gardner · 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)