Cheap and Secure Web Hosting Provider : See Now

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

, ,
Problem Detail:

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?

#### Answered By : Lieuwe Vinkhuijzen

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

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62740

3.2K people like this