complexity of a Sequential algorithm - min suffixes

Question

In a Sequential algorithm (not parallel)..

is the best complexity for finding the min in each suffix of an array would be O(nlogn) ?could it be O(n)? if not? why?

INPUT:
array={x1,x2....xn}

OUTPUT:
X= {min(x1,x2....xn),min(x2....xn),(x3,x4....xn)...........min(xn-1,xn),xn}

Answer 1

Using the fact

min(x1,x2,...,xn) = min(x1,min(x2,x3,...,xn))

You can see that you can use a DP algorithm to solve for X in O(n)

Pseudocode

Min-Suffixes(input)
    n = input.length
    let output = new array of size n
    output[n] = input[n]
    for i = n-1 to 1
        output[i] = min(output[i+1],input[i])
    return output