Running time of adding $n$ items

Question

I am trying to calculate how many binary additions it takes to add $n$ items. I see that with each iteration of binary addition, I am left with $n/2$ items so I see that it would take $\log_2 n$ iterations.

By writing out a few examples, I see that it is $n-1$ binary additions to add together $n$ items but I'm wondering how I can prove this.

Is there a formula which which shows $\Sigma (\log_2 \log_2 (\log_2 ...(n))$ or something?

Answer 1

You have $n$ items when you start. Each time you do an addition, instead of the two items, you have only one item (their sum): so the total number of items decreases by $1$.

So as you have $n$ items initially and each addition decreases the number of items by $1$, you need to make $n-1$ additions for the total number of items to reach the final value $1$.

Bonus: In a knockout tournament with $n$ players, how many matches do you need?

Answer 2

Each sum reduces the number of terms by 1. So it takes $n-1$ adds to reduce from $n$ to 1.