What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?

Is it O(n) because the maximum stack size is n, or is it O($n^2$) because there are $n(n+1)/2$ memory references?

  • $\begingroup$ did you mean "... where g(n) is in O(n)"? As state your question doesn't make sense to me. $\endgroup$
    – Jake
    Aug 20 '16 at 2:19
  • $\begingroup$ yes, i mean the function g is O(n) in space complexity $\endgroup$
    – Jack Black
    Aug 20 '16 at 2:47
  • $\begingroup$ Please edit the question to clarify your intent. Don't just leave clarifications in the comments -- we want the question to stand on its own, without people having to read the comments to understand what you are asking. $\endgroup$
    – D.W.
    Aug 20 '16 at 17:14

Space complexity is about the maximum stack size, so this function uses $O(n)=O(\log(x))$ space. Your intuition about this is right: each call to $g$ uses and overwrites memory previously used by the previous call to $g$, so the stack grows to $O(n)$

Why the $\log(x)$ factor? If $g$ uses $O(n)$ memory for an $n$-bit input, then it uses $O(n)=O(|x|) = O(\log(x))$ memory for input $x$, which is of length $|x|=\log(x)$.

  • $\begingroup$ Off-topic: "Les Measurables", that's funny!!! (sorry, re your request, I have nothing to contribute) $\endgroup$ Aug 24 '16 at 8:36

f (x) can be calculated with O (x) space. In practice, if you are interested in speed, you would try to find out if calculating g (n) for x different values can be done faster than n individual calculations. You might find a way to calculate f (x) that is significantly faster than adding x values, but takes more space.

An example: Let g (n) be the same of the divisors of n. f (x) can be calculated almost as fast as a single value g (n) in the worst case.


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.