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?
Best Answer
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.