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
    $\begingroup$ 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. $\endgroup$
    – joriki
    Oct 11 '12 at 23:43
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 12 '12 at 2:45
  • 1
    $\begingroup$ Do you really mean k is fixed? (This implies $2^k$ is fixed too.) $\endgroup$ 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.

  • $\begingroup$ 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. $\endgroup$ Oct 18 '12 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.