0

When i was learning about Big O Notations , while getting to know the binary search algorithm as it requires sorting the array before searching . I had a question that isn't sorting going to take the same amount of time as linear search as it will look at each and every memory locations there is ?

Rushikesh
  • 1
  • 1
    no, sorting+binary search will take way more than just looking at each element with a linear search – Alberto Sinigaglia May 12 '22 at 07:08
  • Sorting algorithms in general take at least O(n log n) time. They need to check each element more than once, and more than a constant number of times. I recommend you read about sorting algorithms, there are great tutorials out there. Binary search is faster than linear, namely O(log n). – Berthur May 12 '22 at 08:13
  • Please provide enough code so others can better understand or reproduce the problem. – Community May 13 '22 at 06:05
  • As stated in https://stackoverflow.com/a/2352321/18980756 lower bound for sorting is `O(n*log(n))`. Exceptions achieving `O(n)` are also stated there: radix sort, counting sort which are **not** comparison-based. – Franck May 13 '22 at 18:04

1 Answers1

1

Sorting an array is typically O(n * log(n)), so it is slower than simply doing one linear search on an unsorted array.

The time savings come in when you need to do more than log(n) searches on the same array. In that case, it's worthwhile to sort it once, then each search only takes an additional log(n) steps.

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880