An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1] is given below.

Let L_i, denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize L_n−1=1.

For all i such that $$0 \leq i \leq n-2$$

$$L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases}$$

Finally, the length of the longest monotonically increasing sequence is max(L₀, L₁,…,L_n−1)
Which of the following statements is TRUE?

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?