# Finding maximum of array consisting of an exponential amount of positive integers

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?

-
You never say what "this problem" actually is. From the title, one might guess that it's finding the maximum of the integers, but the body never says that. – joriki Oct 11 '12 at 23:43
You also don't say how the computation is to be done. If you are restricted to a single processor, the result is much different than if you can use a large number of processors working in parallel. – marty cohen Oct 12 '12 at 2:45
Do you really mean k is fixed? (This implies $2^k$ is fixed too.) – Douglas S. Stones Oct 18 '12 at 13:10

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.
It can be important to account for the "number of bits" (but it's not the bits in $n$, it's the bits in the $x_i$'s, which form the input). For example, if $\log x_1$ and $\log x_2$ grow faster than $O(2^k)$. Then just comparing these two numbers alone will take more than $O(2^k)$ time. – Douglas S. Stones Oct 18 '12 at 13:12