# 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)$.