25
votes
Accepted
Does an algorithm's space complexity include input?
It depends on the chosen convention. I often prefer the convention that considers that the input is not part of the space complexity, for different reasons:
the space complexity of a function answer ...
- 15.5k
25
votes
Accepted
Does space complexity analysis usually include output space?
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 ...
- 81.7k
7
votes
Why is DFS considered to have $O(bm)$ space complexity?
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 ...
- 277k
6
votes
Accepted
Showing strong connectivity is in DSPACE((logn)^2)
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)$...
- 277k
6
votes
Does an algorithm's space complexity include input?
Auxiliary Space: The extra space that is taken by an algorithm
temporarily to finish its work
Space Complexity: Space complexity is the total space taken by the
algorithm with respect to the input ...
- 169
5
votes
Chess Knight minimum moves to destination on an infinite board
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 ...
5
votes
Accepted
Space complexity of string indices: O(1) or O(log|S|)?
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.
- 1,996
5
votes
Chess Knight minimum moves to destination on an infinite board
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 ...
- 504
5
votes
Accepted
Index variable takes up log(n) space?
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$ ...
- 29.5k
4
votes
Memory needed for computational graph
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. ...
- 277k
4
votes
Accepted
Worst Case Space Complexity of Merge Sort and Bubble Sort
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 ...
- 60
4
votes
Accepted
Is there a measure of space usage over time?
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 ...
D.W.♦
- 159k
4
votes
Python: A doubt on time and space complexity on string slicing
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}|)$...
- 277k
3
votes
Why is DFS considered to have $O(bm)$ space complexity?
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 ...
- 3,463
3
votes
Accepted
Recurrence: space complexity to Tournament Method
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 ...
- 277k
3
votes
Accepted
How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?
"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 ...
- 1,624
3
votes
With Memoization Are Time Complexity & Space Complexity Always the Same?
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 ...
- 72.4k
2
votes
Is FKS hashing really linear space?
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 ...
- 277k
2
votes
With Memoization Are Time Complexity & Space Complexity Always the Same?
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 ...
- 13.2k
2
votes
Is the memory usage of total languages deterministic?
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 ...
- 459
2
votes
Accepted
What is the complexity to show this theorem?
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 ...
- 277k
2
votes
Accepted
How large would a database containing perfect knowledge of chess be?
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 ...
- 313
2
votes
Accepted
Chess Knight minimum moves to destination on an infinite board
thanks to matt timmermans by his hint I realized for infinite chess boards no search algorithm BFS, DFS, A*, Dijkstra should be used. just calculate diagonal symmetry and imagine that start point as (...
- 268
2
votes
Space efficient data structure for subsets of [1:n]
Bit vectors fulfill all your requirements.
- 72.4k
2
votes
can similarity transformation be linear transformation?
Linear transformations fulfill two criteria:
T(A) + T(B) = T(A + B)
and
k T(A) = T(k A) (for any scalar k)
What happens if A ...
- 338
2
votes
what will be space complexity for snippet for(i=1 to n) int x=10;?
You are right. Are they saying if we run that loop n times then n different variables having name x will be created? This doesn't happen. Moreover, it is good practice to avoid unnecessary global ...
- 117
2
votes
Accepted
The space complexity of a function that allocates space based on the input value and not size
It is $O(n)$ and, more precisely, $\Theta(n)$.
What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the value of $n$...
- 29.5k
1
vote
Big O space complexity of this isAnagram method
You probably expected the following answer.
Everyone of your friends is correct from her/his own perspective.
All you need to realize is that complexity analysis depends on lots of assumptions. In ...
- 39k
1
vote
Accepted
Does array always have a wasted space of O(n)?
It depends on the algorithm used. Someone made the assumption that when an array has space for n items, and the n+1st item needs to be added, the array would be resized to a size c·n for some constant ...
- 30k
Only top scored, non community-wiki answers of a minimum length are eligible