Question

Download Solution PDF

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64.

Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

This question was previously asked in
GATE CS 2015 Official Paper: Shift 3
Attempt in App
View all GATE CS Papers >
  1. 256
  2. 512
  3. 1024
  4. 2048

Answer (Detailed Solution Below)

Option 2 : 512
Free Tests
View all Free tests >
Free
GATE CS Full Mock Test
65 Qs. 100 Marks 180 Mins
Start Now

Detailed Solution

Download Solution PDF

Concept:

Merge sort algorithm worst case time complexity is O (nlogn)

Data:

T1 (n) =30 seconds, n1 = 64

T2 (n) = 6 minutes

Formula:

T(n) = nlog2n

Calculation:

30 = c × 64 log2(64)

30 = c × 64 log2(26)

30 = c × 64 × 6

6 × 30 = c n2 log2n2

∴ n2 = 512

The maximum input size of a problem that can be solved in 6 minutes is 512

Download Solution PDF
Latest GATE CS Updates

Last updated on Jan 8, 2025

-> GATE CS 2025 Admit Card has been released on 7th January 2025.

-> The exam will be conducted on 1st February 2025 in 2 shifts.

-> Candidates applying for the GATE CE must satisfy the GATE Eligibility Criteria.

-> The candidates should have BTech (Computer Science). Candidates preparing for the exam can refer to the GATE CS Important Questions to improve their preparation.

-> Candidates must check their performance with the help of the GATE CS mock tests and GATE CS previous year papers for the GATE 2025 Exam.

Exams Tests Super Practice

More Sorting Questions

Q1.The Highest Lower Bound on the number of Comparisons in the worst case for comparison-based sorting order of : 
Q2.Which of the following is not a stable sorting algorithm ?
Q3.Match the LIST-I with LIST-II LIST - I Algorithm LIST - II Complexity A. Insertion Sort I. O(log n) B. Binary Search II. O(n2) C. Quick Sort III. O(n - 1) D. Selection Sort IV. O(n log n) Choose the correct answer from the options given below:
Q4.Adjacent elements are compared and swapped in ________ sorting technique.
Q5.Consider the following statements about heap sort algorithm: A. The MAX-HEAPIFY procedure which runs in O lg (n) time, is the key to maintaining the max heap property B. The BUILD-MAX-HEAP procedure, which runs in O lg (n) time, produces max-heap from an unordered input array C. The MAX-HEAP-INSERT, which runs in O (lg n) time, implements the insertion operation D. The HEAP-INCREASE-KEY procedure runs in O (n lg n) time, to set the key of new node of its correct value Choose the correct answer from the options given below:
Q6.What is the average case time complexity of bubble sort?
Q7.The k-Means algorithm is an ______  algorithm.
Q8.Which of the following algorithm design approach is used in Quick sort algorithm?
Q9.What will be the output list after completing first pass of bubble sort on input array 32, 51, 27, 85, 66, 23, 13, 57?
Q10.What is the formula to be used to calculate the total number of comparisons in bubble sort with n elements after k iterations?

More Searching, Sorting and Hashing Questions

Q1.The Highest Lower Bound on the number of Comparisons in the worst case for comparison-based sorting order of : 
Q2.Which open addressing technique is free from Clustering problems ?
Q3.The recurrence relation for binary search algorithm is : 
Q4.Which of the following is not a stable sorting algorithm ?
Q5.Match the LIST-I with LIST-II LIST - I Algorithm LIST - II Complexity A. Insertion Sort I. O(log n) B. Binary Search II. O(n2) C. Quick Sort III. O(n - 1) D. Selection Sort IV. O(n log n) Choose the correct answer from the options given below:
Q6.Adjacent elements are compared and swapped in ________ sorting technique.
Q7.Which of the following is TRUE ? 
Q8.Which collision resolution technique involves maintaining a linked list of collided keys ? 
Q9.Complexity for linear search is 
Q10.Consider the following statements about heap sort algorithm: A. The MAX-HEAPIFY procedure which runs in O lg (n) time, is the key to maintaining the max heap property B. The BUILD-MAX-HEAP procedure, which runs in O lg (n) time, produces max-heap from an unordered input array C. The MAX-HEAP-INSERT, which runs in O (lg n) time, implements the insertion operation D. The HEAP-INCREASE-KEY procedure runs in O (n lg n) time, to set the key of new node of its correct value Choose the correct answer from the options given below:
Suggested Test Series
View All >
GATE Mathematics & General Aptitude (Common for All) Test Series
92 Total Tests with 0 Free Tests
Start Free Test
GATE CSE 2023-24 Test Series
129 Total Tests with   1 Free Tests
Start Free Test

GATE CS Important Links

BooksSyllabusPreparation TipsPaper AnalysisCut OffPrevious Year Papers

More Algorithms Questions

Q1.The Highest Lower Bound on the number of Comparisons in the worst case for comparison-based sorting order of : 
Q2.In what manner is a state-space tree for a backtracking algorithm constructed ? 
Q3.Which open addressing technique is free from Clustering problems ?
Q4.Assume that P and NP are different i.e. P! = NP then for the expression NP-Complete ∩ P = ? Which among the following is correct ? 
Q5.The recurrence relation for binary search algorithm is : 
Q6.The time complexity of solving the Longest Common Subsequence problem using Dynamic Programming is : (m and n are lengths of subsequences) 
Q7.Given the following characteristics : (i) Optimal substructure (ii) Overlapping subproblems (iii) Memorization (iv) Decrease and conquer Dynamic programming has the following characteristics :
Q8.Which of the following is not a stable sorting algorithm ?
Q9.Match the LIST-I with LIST-II LIST - I LIST - II A. Breadth First Search I. LISP B. Depth First Search II. Syntax tree C. Prefix III. Stack D. Infix IV. Queue Choose the correct answer from the options given below:
Q10.Which one of the following is not related to the feed forward networks on the Backpropagation Algorithm
Testbook Edu Solutions Pvt. Ltd.
1st & 2nd Floor, Zion Building,
Plot No. 273, Sector 10, Kharghar,
Navi Mumbai - 410210
support@testbook.com
Toll Free:1800 833 0800
Office Hours: 10 AM to 7 PM (all 7 days)
Company
About usCareers We are hiringTeach Online on TestbookPartnersMediaSitemap
Products
Test SeriesTestbook PassOnline CoursesOnline VideosPracticeBlogRefer & EarnBooks
Copyright © 2014-2022 Testbook Edu Solutions Pvt. Ltd.: All rights reserved
User PolicyTermsPrivacy
Hot Links： teen patti real cash apk teen patti online teen patti gold online teen patti mastar teen patti all