Answer :
Answer:
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<n;i++)
{
tempLength=1;
for(j=i;j<n-1;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)