Ask Question
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)
  1. 26 June, 22:09
    0
    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)
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers