top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

0 votes
493 views
How can we check that a given array is sorted or not in better than O(n)?
posted Jul 28, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

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;
}
answer Jul 28, 2014 by Salil Agrawal
Similar Questions
0 votes

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?

...