My lecture states that search in a sorted array can be done in ω(n).

Why is that? I know it can be done with "normal" search in Θ(n) and with binary search in O(log(n)).

My guess would be, make the algorithm so bad that it is in
ω(n) but that's a kinda silly guess I think.

Thank you all in advance.

  • 4
    $\begingroup$ I suggest you ignore your lecture. $\endgroup$ – Yuval Filmus Feb 18 '17 at 22:39
  • $\begingroup$ I have the solution. It was a multiple choice exercise. My guess was right. You make your search algorithm so bad that's in ω(n). Like just fill a n x n matrix with 1's and you get your ω(n) time. $\endgroup$ – Nimolo Feb 21 '17 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.