Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science Algorithms: Sorting and Searching Searching Names Timing Our Search Scripts

In practice, how often is sorting + binary search preferred over linear search?

I timed the function quicksort_strings.py with output to file sorted.txt, and that function itself took longer than linear_search.py by about a sixth of a second for the hundred thousand names. So, together, sorting the file then using binary_search.py is definitely slower than linear_search.py when trying to find the hundred names in a list of hundred thousand names.

Additionally, the Big-O notation of time complexity for quicksort is O(n*log(n)), which is larger than that for linear search (O(n)). So, would the time complexity for sorting then performing binary search be n*log(n) + log(n)?

In other words, although binary search per se is quicker and has a smaller time complexity than linear search, wouldn't it be slower and have a larger time complexity in practice because it requires sorting in order to work at all?

Supposing that you can't be sure your data is sorted, how large of a pool to search in and/or how many targets to look for would make sorting then using binary search faster than just using linear search on the unsorted data?

In practice, how big is big data--that is, how often do we encounter cases in which sorting + binary search is faster than linear search without sorting?

1 Answer

Steven Parker
Steven Parker
231,236 Points

Time time required for a linear search is relative to the position of the item found. So if you were looking for something near the beginning of the list that would give linear search a big advantage.

Also, in practice, sorting is not done as part of a search. The list would be maintained in sorted order, and when something is needed only the binary search is performed. So with that in mind, it should be clear that binary search offers a significant efficiency advantage on lists of even moderate size. And the savings is huge when working with "big data".