-1

Here the professor said that, Tournament sort needs (n-1) + 2(n-1)logn comparisons.

{Where (n-1) for calculating Maximum or say creating Tournament structure and 2(n-1)logn for other elements to sort}

Why did the professor leave out the number of comparisons needed to find the Minimum? Because to calculate min elements we need (n/2 - 1) comparisons.

Here logn means log n to the base 2

I am watching NPTEL lecture https://youtu.be/NU77XIX-wro (Video Time - 25:50)

0

Because of "sorting" and "leaving out" I think, you refer to the big O notation.

Quoting:

If the function f can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n).

In (n-1) + 2(n-1)logn, n grows not as fast as n*log(n).

  • Thanks @User for your reply. I agree that if we don't use Min -1 the structure get distrub. So calculating Minimum is nessesary. And for calculating Minimum we need N/2 -1 compression, isn't it? So why the professor haven't includ it while calculating the total comparison. May be I am wrong or missing something but I am highly confused. Need Help. NOTE :- The Professor haven't use the Any concept of Asymptotic Notation. – Bhaskar Aug 12 '17 at 18:16
0

It looks like finding the minimum is not one of the steps of the algorithm. So the number of comparisons required in order to find the minimum is irrelevant, since that step is never even performed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.