Problem Detail: 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)?
Asked By : LoveRight
Answered By : D.W.
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 http://cstheory.stackexchange.com/q/4556/5038 and http://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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37333 Ask a Question Download Related Notes/Documents
