Discussion
Suppose there are \(\log_{n}\) sorted lists of n \(\log_{n}\) elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)
Answer: A
The key, option A, takes the lists to be log n in number and n divided by log n in length, so that the total number of elements is n. This is read from the key, since as printed the stem shows 'n log n' and not the quotient. With the heap method the merge keeps one element from each of the k = log n lists in a heap and removes the smallest each time. Each of the n steps costs \(O(\log k)\), so the time is \(O(n \log k) = O(n \log \log n)\). The other options, \(\theta(n \log n)\), \(\Omega(n \log n)\) and \(\Omega(n^{3/2})\), are larger than this bound, and a reviewer may wish to check the stem against the key.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development