I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well.
On to my question. Before I do, this is a class question that has been asked, answer, and considered to be over; however, I'm struggle accepting the answer. For this reason, I'm here hoping someone can word it in a way that I understand it.
The problem is as follows:
Show that if n is a power of 2, tournament sort requires O(n lg n) comparisons.
I refer to a rooted tree graph of six levels (0-5) with the vertices doubling at each level: i.e 1, 2, 4, 8, 16, 32. I see a pattern very similar to binary. I'm not implying the problem is binary related, but it is powers of 2 and I'm very comfortable with binary.
Using that 2^5 = 32, n=32; therefore, n is a power of 2. No argument here. Now I read the problem to say that 32log32 (nlogn) will result in the number of comparisons. The aide answering my question said, "the calculated results of the nlogn were immaterial. I just needed to know there were 5 levels down, and therefore 5 levels up." Additionally, he kept referring to 5log5 which I still don't see a result that makes any sense to me.
As I study the question, I read it to say that the nlogn should provide me with a number of comparisons, based on n. I cannot make that happen with a known values.
Can someone please help me to follow this better?
If you have 32 (general case : 2^k) leaves, than after the first round of comparisons, the largest key will go up, after the second round, it will anew go up, ..., so that you will need at most 5 (general case : k) rounds. and in a round, you have 2*32-1 (general case : 2^(k+1)-1) comparison . so at the end, you have at most $(2^{k+1}-1)*k = (2^{k+1}-1)*log_2(2^k) = O(2^k log_2(2^k)) $ comparisons.