nlogn/2

The Gateway to Computer Science Excellence

+1 vote

0

@Anu sir,

i cant explain it completely here because it require too much working, but can give hint how i did it.

merging two lists we need in worst case (m+n-1) comparsions...

calculating with above fact taken into account, it will give nlogn-n+1 = O(nlogn) comparisons

0

I think question is talking about 2-way merge sort.

At the last level, there will be n/2 comparisons.

At the second last level, there will be n/2 list each conataing 2 elements, worst case comparisons (m+n-1) = 3

there are n/4 list comparisons, each needs 3 comparisons.

total comparisons: 3*n/4

at the third last level, there are n/4 lists each having 8 elements, n/8 pairs for for comparison, worst case number of comparisons = 8+8-1 = 15

at 4th last level, each list contains 16 elements, n/8 total lists, and n/16 pairs for comparisons. worst case comparisons = 16+16-1 = 31

total comparisons =

=n/2 + 3*n/4 + 15*n/8 + 31*n/16 + .... (in worst case)

In question, minimum number of comparisons are asked:

at last level = n/2 comparisons

at second last level = n/2 lists, n/4 pairs, each needs 2 comparisons, total comparisons = (n/4)*2 = (n/2)

Aat third last leevl = n/4 lists, n/8 pairs, best comparisons = 4, total comparisons = (n/8)*4 = n/2

such way, logn terms of (n/2) total cost = (nlogn/2).

At the last level, there will be n/2 comparisons.

At the second last level, there will be n/2 list each conataing 2 elements, worst case comparisons (m+n-1) = 3

there are n/4 list comparisons, each needs 3 comparisons.

total comparisons: 3*n/4

at the third last level, there are n/4 lists each having 8 elements, n/8 pairs for for comparison, worst case number of comparisons = 8+8-1 = 15

at 4th last level, each list contains 16 elements, n/8 total lists, and n/16 pairs for comparisons. worst case comparisons = 16+16-1 = 31

total comparisons =

=n/2 + 3*n/4 + 15*n/8 + 31*n/16 + .... (in worst case)

In question, minimum number of comparisons are asked:

at last level = n/2 comparisons

at second last level = n/2 lists, n/4 pairs, each needs 2 comparisons, total comparisons = (n/4)*2 = (n/2)

Aat third last leevl = n/4 lists, n/8 pairs, best comparisons = 4, total comparisons = (n/8)*4 = n/2

such way, logn terms of (n/2) total cost = (nlogn/2).

0

@Manu,

try to take for n=4, with (nlogn / 2) it will give 4 comparisons, but actually it will take 5 comparisons.

try to take for n=4, with (nlogn / 2) it will give 4 comparisons, but actually it will take 5 comparisons.

0 votes

I think the formula for the no of comparison should be n/2 + 3*n/4 + 7*n/8 + 15*n/16 + ....

=(2-1)n/2 + (4-1)*n/4 + (8-1)*n/8 + 1(6-1)*n/16.....

=(n-n/2)+(n-n/4)+(n-n/8)+......log n times

=nlogn-(n+n/2+n/4.........)

=nlogn-n+1 is the answer for no of comparisons in worst case but in the given question it is asking about the minimum no of comparisons i.e. in best case for every level it will perform n/2 comparisons logn times.So the answer is nlogn/2.

We have to keep in mind that no of comparisons is not equal to asymptotic time complexity

=(2-1)n/2 + (4-1)*n/4 + (8-1)*n/8 + 1(6-1)*n/16.....

=(n-n/2)+(n-n/4)+(n-n/8)+......log n times

=nlogn-(n+n/2+n/4.........)

=nlogn-n+1 is the answer for no of comparisons in worst case but in the given question it is asking about the minimum no of comparisons i.e. in best case for every level it will perform n/2 comparisons logn times.So the answer is nlogn/2.

We have to keep in mind that no of comparisons is not equal to asymptotic time complexity

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,167 answers

193,840 comments

94,030 users