Search code examples
sortingtime-complexitybinary-search

What is better sorting an unsorted array and binary searching n times or linear searching unsorted array n times?

I wanted to search an array which is unsorted, n times to find paticular set of values less than a given number other than array elements. So is it better to sort and then do a binary search n times or to linear search in unsorted array

Solution

  • If n is small you have a performance advantage to search in an unordered array:

    n = small

    Sorting: Zero time (0)
Searching: Linear time (n)    

Sum: Linear time (n)

    n = big

    Sorting: Zero time (0)
Searching: Quadratic time (n²) 

Sum: Quadratic time (n²)

    If n is big better sort the array before and then do binary search:

    n = small

    Sorting: Linearithmic time (n log n)
Searching: Logarithmic time (log n)

Sum: Linearithmic time (n log n)

    n = big

    Sorting: Linearitmnic time (n log n)
Searching: Linearithmic time (n log n)

Sum: Linearithmic time (n log n)

    I can't tell you where is the tipping point but you can do some experiments. ;)