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?

  • 2
    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.2012-10-11
  • 1
    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.2012-10-12
  • 1
    Do you *really* mean k is fixed? (This implies $2^k$ is fixed too.)2012-10-18

1 Answers 1