Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Assume that a mergesort algorithm in the wors...
Start Learning for Free
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?
- a)256
- b)512
- c)1024
- d)2048
Correct answer is option 'B'. Can you explain this answer?
Most Upvoted Answer
Assume that a mergesort algorithm in the worst case takes 30 seconds f...
Time complexity of merge sort is Θ(nLogn)
c*64Log64 is 30
c*64*6 is 30
c is 5/64
c*64*6 is 30
c is 5/64
For time 6 minutes
5/64*nLogn = 6*60
nLogn = 72*64 = 512 * 9
n = 512.
5/64*nLogn = 6*60
nLogn = 72*64 = 512 * 9
n = 512.
Free Test
FREE
| Start Free Test |
Community Answer
Assume that a mergesort algorithm in the worst case takes 30 seconds f...
Explanation:
To solve this problem, we can use the concept of time complexity of mergesort algorithm which is O(n log n) in the worst case.
We know that the worst case time complexity of mergesort algorithm for an input of size n is given by:
T(n) = 2T(n/2) + n
where T(n/2) represents the time taken to sort half of the input size and n represents the time taken to merge the two halves of the input array.
Using this formula, we can find the time taken by mergesort algorithm for an input of size 64 in the worst case as follows:
T(64) = 2T(32) + 64
T(32) = 2T(16) + 32
T(16) = 2T(8) + 16
T(8) = 2T(4) + 8
T(4) = 2T(2) + 4
T(2) = 2T(1) + 2
T(1) = 1
Substituting the values of T(1), T(2), T(4), T(8), T(16), T(32) and T(64), we get:
T(2) = 4
T(4) = 10
T(8) = 22
T(16) = 46
T(32) = 94
T(64) = 190
Therefore, the worst case time taken by the mergesort algorithm for an input of size 64 is 190 seconds.
Now, we need to find the maximum input size of a problem that can be solved in 6 minutes (i.e. 360 seconds).
We can use the following formula to find the maximum input size:
T(n) = C * n * log n
where T(n) is the maximum time taken for an input of size n, C is a constant factor, and log n is the time complexity of the mergesort algorithm.
Substituting the values of T(n), C and log n, we get:
190 = C * 64 * log 64
C = 190 / (64 * 6)
C = 0.496
Now, we can use this value of C to find the maximum input size as follows:
360 = 0.496 * n * log n
n * log n = 725.81
n = 512 (approx.)
Therefore, the maximum input size of a problem that can be solved in 6 minutes is approximately 512.
Hence, the correct answer is option B.
To solve this problem, we can use the concept of time complexity of mergesort algorithm which is O(n log n) in the worst case.
We know that the worst case time complexity of mergesort algorithm for an input of size n is given by:
T(n) = 2T(n/2) + n
where T(n/2) represents the time taken to sort half of the input size and n represents the time taken to merge the two halves of the input array.
Using this formula, we can find the time taken by mergesort algorithm for an input of size 64 in the worst case as follows:
T(64) = 2T(32) + 64
T(32) = 2T(16) + 32
T(16) = 2T(8) + 16
T(8) = 2T(4) + 8
T(4) = 2T(2) + 4
T(2) = 2T(1) + 2
T(1) = 1
Substituting the values of T(1), T(2), T(4), T(8), T(16), T(32) and T(64), we get:
T(2) = 4
T(4) = 10
T(8) = 22
T(16) = 46
T(32) = 94
T(64) = 190
Therefore, the worst case time taken by the mergesort algorithm for an input of size 64 is 190 seconds.
Now, we need to find the maximum input size of a problem that can be solved in 6 minutes (i.e. 360 seconds).
We can use the following formula to find the maximum input size:
T(n) = C * n * log n
where T(n) is the maximum time taken for an input of size n, C is a constant factor, and log n is the time complexity of the mergesort algorithm.
Substituting the values of T(n), C and log n, we get:
190 = C * 64 * log 64
C = 190 / (64 * 6)
C = 0.496
Now, we can use this value of C to find the maximum input size as follows:
360 = 0.496 * n * log n
n * log n = 725.81
n = 512 (approx.)
Therefore, the maximum input size of a problem that can be solved in 6 minutes is approximately 512.
Hence, the correct answer is option B.
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Top Courses for Computer Science Engineering (CSE)View all
Question Description
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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer?.
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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer?.
Solutions for 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer?, a detailed solution for 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? has been provided alongside types of 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice 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?a)256b)512c)1024d)2048Correct answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup