2
$\begingroup$

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?

  • 1
    Do you *really* mean k is fixed? (This implies $2^k$ is fixed too.)2012-10-18

1 Answers 1

3

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.

  • 0
    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.2012-10-18