Answer TRUE or FALSE.

The lower bound in the worst case for the problem of searching an unsorted array is \Omega(n) because this is the worst case cost of the sequential search algorithm.

False
  • True
  • False

While it is true that sequential search is \Omega(n) in the worst case, this is not the whole story.

Just because the best algorithm that we happen to know has a certain cost, that does not mean that there is no better algorithm.

The reason that search in an unsorted array has a lower bound of \Omega(n) is because we can prove that any algorithm MUST look at every element (in some order) in the worst case.