Question

Suppose our software program is searching through words used by social media users to find uses of keywords. The data holding the users typed words is in sorted order, sorted lexicographically, like apple comes before ’astronomer’. You can assume that all steps needed to check each letter in one typed word are all considered as one constant complexity step. (a) Based on your experience with the material, which form of search could be used to achieve good performance for this purpose? (b) Explain what the time complexity and Big O of your chosen search would be, and why it applies

Answer 1

In case of any queries, please revert back.

(a)Here,the whole data has been sorted in lexicographical order. Which means data is sorted in alphabetical terms.

Binary Search is a set example that searches a sorted array in the best possible way.

We simply compare letter wise in the words. if the middle word of that data is greater, we search the smaller data part. Otherwise, we search the larger part of data. This divides the time complexity.

(b) Time complexity of binary search is O(log n). This is because at each step, we divide the search into parts of half.

So, we have T(n)=T(n/2) + c