2
$\begingroup$

That's what I'm formally asking:

Let the algorithm $A$ have the worst-case time complexity $\Theta(f(n))$, such that for any algorithm $B$ with the worst-case time complexity $\Theta(g(n))$ doing the same job as $A$, $g(n) \in \Omega(f(n))$. Let $\Theta(s(n))$ be the worst-case space complexity for the algorithm $A$, such that for any algorithm $B$ doing the same job as $A$, having the same time complexity as it and the space complexity $\Theta(p(n))$, $p(n) \in \Omega(s(n))$. Can $f(n) \in o(s(n))$?

Intuitively, for any such algorithm, we need to spend $O(1)$ time for each $O(1)$ of the memory, therefore the space complexity would be worse or the same as the time complexity, that results in the "no" answer to the question. It's just an intuition anyway, that's why I'm asking the question here.

$\endgroup$
1
  • 2
    $\begingroup$ I would say, depends on the computation model. Perhaps in quantum computing it is possible. In classic computing you need 1 operation to alter contents of a memory cell, so to change contents of $n$ cells, you need at least $n$ operations. If you allow parallel computing, it depends on how you count it. $\endgroup$
    – rus9384
    Jan 21 at 13:00

0