CS301 Data Structures GDB No.1 Solution Fall Semester 2013


Total Marks 5
Starting Date Tuesday, January 22, 2013
Closing Date Thursday, January 24, 2013
Status Open
Question/Description

GDB’s Instructions

You need to provide precise and to the point answer, avoid irrelevant details.
Try to justify your answer mathematically.
Copy from the internet will get zero marks.

GDB’s Topic

The better algorithm for sorting a set of data has O(nlogn) running time, linear search has O(n) running time and binary search has O(logn) running time, where big O is a notation for expressing running time of algorithms you may treat these running times like n, nlogn, logn.

Sponsored Links

On the basis of this information, consider the scenario that there is a large set of unsorted data, you need to perform “n” searches on this data. For this you have the following two options.

Perform “n” linear searches
First sort this data in O(nlogn) time and then perform “n” binary searches.

Which option will you choose? Justify your answer mathematically.