(Almost) every algorithm runs in exponential time, or merely in 'pseudo-polynomial' time.

Given a list of integers, does it contain the number 2?

O(N), where N is the size of input, right?

Wrong. Express N as 2^b, and it's O(2^b) -- exponential runtime.

So every problem (basically) is as hard as the allegedly 'extremely difficult' factorization problem and subset sum problem.

Why do computer scientists make believe problems like the factorization problem and subset sum problem are any harder for a computer to solve than one of the first algorithms you write in your intro to cs class?

  • 17
    $\begingroup$ When you discover that all computer scientists are idiots, you should stop for a second, and consider whether you too are a computer scientist. $\endgroup$ – Andrej Bauer Mar 5 '17 at 18:11
  • 2
    $\begingroup$ It appears that you might have created multiple accounts. (That's why you can't comment; if you retain access to your original account that you used to ask the question, then you can use it to comment on answers to the question you asked.) You can merge your accounts. See also register your account. $\endgroup$ – D.W. Mar 5 '17 at 18:58
  • 1
    $\begingroup$ By this logic, you can argue there are no algorithms in EXP either. If one is O(2^n), just substitute for b = 2^n => O(b) / linear time $\endgroup$ – DaveBensonPhillips Mar 5 '17 at 18:59
  • $\begingroup$ @DaveBensonPhillips A linear-time algorithm is still in EXP. You need to go the other way: substitute $n=2^b$ and then claim that the resulting $\Theta(2^{2^b})$ would mean that the problem is actually in 2EXP. No, wait, 3EXP because $b=2^c$. Er, 4EXP, ... $\endgroup$ – David Richerby Mar 5 '17 at 19:58
  • $\begingroup$ Bad question :-| $\endgroup$ – aminography Sep 20 '18 at 10:56

Actually you're wrong. In the example you give, you take a list of integers, but even with binary representation for the numbers in the list, the input length is still linear in the number of elements of that list, so the algorithm is polynomial ( not pseudo ). Complexity is always measured in respect to the total input length, not some arbitrary number ( b ) you choose that's correlated to the input.

Pseudo-polynomial only works for problems where your input basically consists of numbers, or lists of numbers, and that it becomes difficult only when the numbers are very large. But many problems aren't in this configuration, think of graphs for example.

Response to the other answer : Sure, it may be in O(N) for a bounded element size, but N isn't the length of the input, the length of the input is the sum of the logarithms of every element, and the dynamic programming algorithm is not polynomial in the logarithm of the elements. It's not taking a lot of small elements that makes it hard, it's taking many very big elements. Also, you could try being less arrogant when asking questions or responding : when you are wrong it just comes off as stupid and pretentious.

  • 5
    $\begingroup$ Welcome to the site, Felix! You've posted a couple of nice answers, so I hope you hang around. $\endgroup$ – David Richerby Mar 5 '17 at 18:04

The premise of your question is mistaken.

The complexity is expressed as a function of the length $n$ of the input. "Does the input contain a specific, fixed bit pattern" (e.g., does it contain the number 2) can be done with a linear scan of the input: it is a linear time algorithm. The fact that you can write $n=2^b$ is irrelevant: we measure complexity with respect to $n$, not respect to $b$.


Perhaps there are some misunderstanding regarding how one arrive at the time complexity and whether or not a problem is in P. However, you are on the right path. Allow me to paraphrase the original problem:

Given a list of $N$ integers, does the list contain the number 2?

Now, suppose each integer is represented using $b$ bits. In other words, each of these N integers are $< 2^b$. Hence, the input size is $Nb$ ($N$ integers, each uses $b$ bits).

To perform a linear search on this list, we simply look at these $Nb$ bits and split them into groups of $b$ bits (we end up with $N$ groups). We then compare each of the $b$ bits with the binary representation of 2 prepended with $b-2$ 0 bits. We know that we can perform each of these comparison in $O(b)$ time (by iterating through the bits). We perform $N$ such comparisons. Hence, the overall runtime is then $O(Nb)$, which is linear with respect to the input size (which is $Nb$).


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.