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.