1
$\begingroup$

For example:

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

Is there a way to increase the space complexity to something like O(n^2) that would guarantee that the time complexity would decrease?

$\endgroup$
1
$\begingroup$

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

First of all we do not know any exponential or sub-exponential time algorithm that requires only $O(1)$ space, having said this, it is difficult to reason about a hypothetical algorithm "A" because the spatial and temporal complexity are closely linked to the functioning of the algorithms and are (generally) proportional to each other, however, the answer to your question is no.

Let's try to reason starting from a $3SAT$ instance. Now we know that $3SAT$ is NP-Complete (best known time complexity for $3SAT$ is currently $O(k^n)$ with $ K=1.439$ for a deterministic algorithm) and $3SAT$ $∈$ PSPACE , in fact space complexity of $3SAT$ is $O(n)$. Now it is difficult to imagine how increasing the space to a constant $k$ (in your question $k = 2$) may lead to a decrease in the execution time of the algorithm that solves $3SAT$ ... in fact always keep in mind that an increase in space also corresponds to a proportional increase over time. Let me conclude by recalling the relationships between temporal and spatial complexity classes for which we believe all inclusions to be strict:

$L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE$

$\endgroup$
  • $\begingroup$ "we do not know any exponential or sub-exponential time algorithm that requires only 𝑂(1) space" I don't understand this, sharing an example. For primality testing; If I have an algorithm that just keeps guessing a number, then this would be O(1) space right? Because we discard the number if it does not factor and check a different number. $\endgroup$ – WeCanBeFriends Jun 20 at 16:19
  • $\begingroup$ $O(1)$ means that space is constant, it does'nt grow with the input size. It is easy to demonstrate that performing the test on $n = 1000000000000000000000000000000000000$ requires a different space than the test on $n = 3$ $\endgroup$ – Yamar69 Jun 20 at 16:27
  • $\begingroup$ Ohh, I think I understand. Although we are checking and removing the numbers. For n = 1000000000000, we require some amount of bits in reserve. But for n = 3, all numbers only require two bits. Is this correct? Even though the number of space required while running the algorithm does not change, the space that we must reserve grows with the input size. $\endgroup$ – WeCanBeFriends Jun 20 at 17:48
  • $\begingroup$ @WeCanBeFriends absolutely correct :) $\endgroup$ – Yamar69 Jun 20 at 18:03

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.