How can we check that a given array is sorted or not in better than O(n)?

Question

Given a string S and set of strings U. Find the length of longest prefix of S that can be formed using strings in U.

For example you have following -

S= “absolute”
U={“abs”,”xyz”,”ol”,”te”}

Answer: 5 i.e "absol"

Now the task is to have the algorithm/program for the above problem, please help me with this?

Answer 1

Try something like this to do in the half time then o(n) but yes it is still o(n). Can not think better then o(n)...

bool IsSorted(int arr[], int length)
{
  int l = length;
  for (int i = 0; i < l/2 + 1 ; i++)
  {
    if (arr[i - 1] > arr[i] || arr[l-i] < arr[l-i-1])
    {
      return false;
    }
  }
  return true;
}