1
$\begingroup$

I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All on deterministic turning machine)

If there exists an algorithm that uses O(1) space to solve the same probelm, what will be its lowest time complexity?

To ask in another way, if space complexity decrease from O(n) to O(1), what at least time complexity will increase from O(n+m)?

$\endgroup$
  • $\begingroup$ Zero is $O$ of everything. $\;\;\;$ Do you mean$\;$ $\Theta$ $\hspace{-0.03 in}(n\hspace{-0.04 in}+\hspace{-0.04 in}m)\:$? $\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Jan 17 '15 at 23:05
1
$\begingroup$

It depends on the problem. There's no general rule.

The running time could be as low as $O(n+m)$: for some problems, there exists an algorithm with running time $O(n+m)$ and $O(1)$ space. (Think about finding the maximum of an array with $n+m$ elements, for example.)

The best possible running time could also be as arbitrarily large. For instance, think of analyzing connectivity in graphs: given a graph and two vertices $s,t$, determine whether there's a path from $s$ to $t$. Let $n$ denote the number of vertices and $m$ the number of edges in the graph. There is a simple algorithm with running time $O(n+m)$ and space complexity $O(n)$, namely, depth-first search. However, there is no known algorithm whose running time is polynomial in $n$ and $m$ and that uses only $O(1)$ space.

See also https://cstheory.stackexchange.com/q/4556/5038 and https://cstheory.stackexchange.com/q/832/5038 for more technical details on this.

Terminology nitpick: problems have a complexity; algorithms have a running time. the complexity of a problem is the running time of the best algorithm for that problem.

$\endgroup$
  • $\begingroup$ I know space complexity will not exceed time complexity. Is there any theorem telling us the lower bound of space complexity? $\endgroup$ – Gqqnbig Jan 18 '15 at 8:14
  • $\begingroup$ @LoveRight, no, just as there is no general theorem telling us the lower bound on the time complexity of a problem. But remember, this is a question-and-answer site. Please avoid follow-up questions in comment threads. Each question should be posted separately in its own question. $\endgroup$ – D.W. Jan 18 '15 at 18:32

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.