# Decrease space complexity, how will time complexity increase?

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)?

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

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.