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)?
Decrease space complexity, how will time complexity increase?
complexity theory
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.