Chapter 2, Problem 7E

Explanation of Solution

Length of longest subarray:

Given an integer array that is in increasing order, finding length of longest subarray that contains numbers that could be arranged in a continous sequence.

Worst case complexity analysis:

Refer section 2.7 in chapter 2 for given algorithm

• If line for(i=0, length = 1;i<n-1;i++) is been replaced by line for(i=0, length =1; i<n-1 && length<n-i; i++) in the given algorithm.
• The best case remains O(n), when numbers in array maintain decreasing order.
• For each n-1 executions of outer loopthe inner loop is been executed just once.
• For an ordered array, inner loop executes n-1 times and outer loop executes only once, which denotes best case.
• The worst case complexity of algorithm is still $O\left(n^2\right)$.

Worst case efficiency:

Yes, the efficiency of the worst case is still $O\left(n^2\right)$