1
$\begingroup$

So In a review section, our professor asked:

Given integers $N$ and $M$

Is $O(N+M)$ exponential or polynomial.

It's exponential, but I just don't see how that is. I would have thought it's linear.

$\endgroup$
  • $\begingroup$ See also here. $\endgroup$ – Raphael Dec 12 '13 at 12:33
8
$\begingroup$

Exponential or polynomial in what? As stated, it's clearly polynomial in $M$ and $N$.

The complexity of algorithms is given in terms of the length of the input. If an algorithm receives $M$ and $N$ as input, written in binary, then $M+N = O(2^\ell)$, where $\ell$ is the length of the input in bits.

You should ask your professor for clarification. S/he knows what s/he actually said and what the context was; we're just guessing.

$\endgroup$
3
$\begingroup$

There must have been some miscommunication. It's not exponential, unless there is some additional context that we're missing. (e.g., if $M=2^N$, then $N+M=O(2^N)$ is exponential in $N$)

$\endgroup$

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.