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

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?

• did you mean "... where g(n) is in O(n)"? As state your question doesn't make sense to me. – Jake Aug 20 '16 at 2:19
• yes, i mean the function g is O(n) in space complexity – Jack Black Aug 20 '16 at 2:47
• 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. – 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)$.

• Off-topic: "Les Measurables", that's funny!!! (sorry, re your request, I have nothing to contribute) – John Forkosh 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.