Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

1 Answer 1

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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