# Tag Info

## Hot answers tagged space-analysis

19

Typically, we consider space complexity in terms of Turing machines with: one read-only input tape one write-only output tape however many read-write working tapes you want. The space usage is the number of cells used on the working tapes, so input and output space typically aren't counted. (See, e.g., Section 2.5 of Papadimitriou.) Obviously, we don't ...

13

Quicksort: For quicksort, your intuition about recursion requiring O(log(n)) space is correct. Since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log(n)) space complexity. Mergesort: Since mergesort also ...

9

When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where: $$C_i = \frac{1}{i+1} { 2i \choose i }$$ are the Catalan numbers. Using Stirling's approximation, we find: $$\log C_{2n} = 2n - O(\log n)$$ So to represent a ...

7

In my opinion you are not quite right... During the loop, when you return from foo(i), the spaces used by the call foo(i) is released (I mean, the stack pointer is back to the previous position). So actually foo(i) only uses 1 more AR than foo(i - 1). The space cost should be O(n). This can be verified by running the code with foo(25) and specify a stack ...

7

It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which nodes you have already visited. Suppose that you run it on a complete $b$-ary tree of depth $m$. We can identify nodes in their tree with words over $[b]$ of ...

6

You don't need to pass $G$ every time, since it doesn't change across calls. You can think of it as a global variable, which is stored only on the input tape. The other parameters take only $O(\log n)$ steps, and since the depth of the call stack is also $O(\log n)$, in total this uses up $O(\log^2 n)$ space on the work tape.

6

It's hard to know for sure from what you've written, but I suspect what you're doing wrong is that you're considering what the space requirement would be for a complete graph. For a complete graph, the space requirement for the adjacency list representation is indeed $\Theta(V^2)$ -- this is consistent with what is written in the book, as for a complete ...

5

Yes, you need up to $n$ stack frames for the recursion. Therefore, you'll need $\Theta(n)$ space for these stack frames.

5

These are correct (unless you explicitly specify a non-standard model of computing): $O(1)$ space, $O(1)$ words of space, $O(\log|S|)$ bits of space.

5

The easiest way to solve this problem is to greedily move in the best direction until you get within 100 squares or so, and then A* from there. Figuring out exactly how close you can get before you have to switch to A* is an interesting problem, but 100 squares away will surely be fine, and A* from there fits into a reasonable amount of memory. Also note ...

5

There is a closed form solution for finding the minimum number of moves the chess knight needs to move a specified displacement on the infinite chess board. Let $g$ be the requisite displacement expressed as a Gaussian integer; the real part of $g$ will be the horizontal displacement, and the imaginary part of $g$ will be the vertical displacement. Then we ...

4

Your problem sounds similar to one-shot (black) pebbling. Wu, Austrin, Pitassi, and Liu, in their paper titled Inapproximability of treewidth, one-shot pebbling, and related layout problems (J. Artificial Intelligence Res. 49 (2014), 569–600), show that it is (probably) hard to compute the optimal cost (which corresponds to your memory).

4

Sure. Of course, you are absolutely right, that time complexity and space complexity don't capture the whole story. No one metric is likely to. There are many ways one could plausibly distinguish between those two programs. For instance, one could ask about average space usage (averaged over the lifetime of the program). These metrics might be harder to ...

4

Typical implementations of Merge sort use a new auxiliary array split into two parts, a left part and a right part. This extra space is the reason for the O(n) space complexity. During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space. int leftPartition[] = new int[ leftPartitionSize ]; int ...

4

If you have a variable $x$ that can represent any number from $0$ to $n-1$ (or any value from a set of of $n$ possible values, really), such an the index of an array of $A[0 \dots n-1]$ of $n$ elements, then $x$ needs to use at least $\lceil \log_2 n \rceil = \Omega(\log n)$ bits. This is because there are $2^b$ combinations for the values of $b$ bits. Then, ...

3

There are two points here to make: In case you introduce into the stack all the descendants of the current node, then effectively, the space complexity is $O(bd)$ where $b$ is the branching factor and $d$ is the maximum length. Yuval Filmus' reply refers to this case indeed. However, note that in general $d$ is much much larger than $b$. Moreover, in many ...

3

First of all, when talking about space complexity, we need to make sure what exactly we are counting. There are two main issues: Are we counting the space taken by the input? How much space does a variable like mid or mml take? How much space does the return address take? Regarding the first issue, usually we're not counting the space taken by the input; ...

3

There are plenty examples for which you need $\omega(1)$ time to compute each table entry or do not need to keep all table entries. An example for the former would be CYK; for the latter memoized Fibonacci and Bellman-Ford.

3

You seem to be confusing the behaviour of a specific graph with the worst-case behaviour. A specific digraph has some given edge set $E$. $|E|$ could be as big as $|V|(|V|-1)$ but it could be much smaller. To represent a specific digraph using adjacency lists, you need one list per vertex. The list for vertex $x$ contains every vertex $y$ ...

3

"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access. From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012): Blocking a matrix multiply routine works by partitioning the matrices into submatrices and then exploiting the mathematical fact that these submatrices can be manipulated ...

3

The best algorithm must certainly depend on the environment. What type of system is your client? What type of system is your server? What kind of transport system stands between them? If, for example, your clients are Raspberry Pis then it is likely you want to reduce the amount of work you need to do on the client end - take the log(n) option. If, your ...

3

The running time of string concatenation depends on how it is implemented. It is impossible to tell whether new_word += i takes $O(1)$ or $\Theta(|\text{new_word}|)$ or anything else unless you know more about Python. Moreover, looking around stackoverflow, it seems that the complexity depends on which version of Python you are using. In contrast, it is ...

2

This is indeed possible. First, notice that for storing $\left\lfloor\frac{N}{x}+1\right\rfloor$ values ($0,1,2,\ldots,\left\lfloor\frac{N}{x}\right\rfloor$), you need $\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil$ bits (which might be larger than $\log\left\lfloor\frac{N}{x}+1\right\rfloor$). This won't stop us though :). We first ...

2

First of all BST has not $\Omega(logn)$ access, it has $\Omega(n)$. What you really need is AVL or RBT tree, self balancing trees to maintain logarithmic access. 1) BST you have to use two pointers (to left and right child) and one variable for data. This is whole footprint. Additionally you have to assign root to some variable. For AVL you may add height ...

2

Because total programs cannot run forever they cannot use infinite memory. You can know maximum, and best case cost from looking at what algorithm is implemented. Checkout these wikipedia pages to see the relationship between different grammars, algorithms, and machines: "https://en.wikipedia.org/wiki/Complexity_class" "https://en.wikipedia.org/wiki/...

2

For each $i,j$ keep track of the last $k$ for which the value $d_{ij}^{(k)}$ was changed. That must be the highest value on the shortest path from $i$ to $j$. The actual path can be retrieved recursively. Added. A simpler solution. Keep track of array $n_{ij}$ of vertices, giving the next vertex on the shortest path from $i$ to $j$. Whenever $d_{ij}^{(k)}$ ...

2

This is not a general rule. It is very possible for a dynamic programming algorithm to have greater time complexity than space complexity (but obviously not the other way around, since we spend at least $O(1)$ time per instance). For instance, you mention that the dice sum problem can be solved in $O(D*T)$ time and space (if we let $D$ be the number of dice ...

2

Space is counted in machine words rather than in bits. A machine word is allowed to contain a member of the universe $U$, and so is $O(\log |U|)$ bits wide. The array $G$ stores hash functions, via their index inside some collection of universal hash functions. The lecture notes don't mention this, but there are collections of universal hash functions of ...

2

This is just SAT in disguise. Given a clause, you can encode the set of assignments falsifying the clause as a sum of the type you indicated. The formula is unsatisfiable iff every assignment falsifies some clause, that is, iff the sum of the regular expressions is $(0+1)^{n-1}$.

2

Claude Shannon indicated that the State Space Complexity (number of legal positions reachable from the initial position in chess) has a lower bound of approximately $10^{43}$. If each entry consists of $20$ bytes, as indicated in your question. The total number of bytes for your database would have a lower bound of $2 * 10^{44}$ which is a very large number ...

Only top voted, non community-wiki answers of a minimum length are eligible