Consider an array of an exponential amount of positive integer numbers, let's say $$ x_1, x_2, \ldots, x_{2^k} $$ for some fixed positive integer $k$.
The question is the following. What is the computational complexity of the problem of finding the maximum of these numbers?
There is something that confuses me--I'll try to explain below.
In general, if we are given $n$ positive integer numbers, I think the best we can do is $n$; i.e. I think the complexity of this problem is $\mathcal{O}(n)$. (Can sombody confirm this? On a side note, how can we know for sure that there is no algorithm that does a better job than this?)
Let us for a moment assume that what I just said (about $n$ etc.) is true. From this it would follow that the complexity of my initial problem (with $k$ as the given input) is $\mathcal{O}(2^k)$. So am I right if I say that the complexity of this problem is $k$?
However, this is when we consider the number $k$ as the given input. But the fact of the matter is that we are given $2^k$ numbers. One could "argue" (reason) as follows: "we are given $2^k = n$ numbers, and the complexity is $\mathcal{O}(2^k)=\mathcal{O}(n)$, so the problem's complexity is linear". Why (if, at all) is this reasoning wrong? So my problem is about what is to be considered as input. More precisely said: what is to be considered an input?
For your second question, finding the greatest of $n$ integers is $O(n)$, you need to compare each number with something or you might miss the greatest, so it can't be less than $O(n)$. An elimination tournament is $O(n)$ so there we are.
The input to the first question is not $k$, nor $2^k$, it is the list of length $2^k$. The answer to the second question says the complexity of this problem is $O(2^k)$ This says the answer to your third question is no, the complexity is $O(2^k)$
When you say the complexity is "linear", that is defined in terms of how you consider the complexity of the input. I have seen the same with algorithms that get a number $n$ as input and have to return some $f(n)$. Sometimes the complexity is stated in terms of $n$, sometimes in terms of the number of bits of $n$, which is $\log_2 n$. Whaddya know, the results are different.