Questions tagged [space-analysis]
The space-analysis tag has no usage guidance.
45
questions
0
votes
0
answers
11
views
Simple example where informed heuristic has larger state space?
So far, I understand that not all informed heuristics can guarantee small search spaces than uninformed, but I am not sure what's a simple example for this type of scenario?
11
votes
5
answers
3k
views
Does an algorithm's space complexity include input?
Consider the Kadane's algorithm for finding maximum subarray within an array:
...
2
votes
0
answers
374
views
Data Structure for finding all bounding boxes that overlap or are contained in a given bounding box
I am looking for a data structure that needs to have very fast and accurate queries to solve the following:
The input:
A set of 3 Dimensional axis-aligned bounding boxes B
A separate 3D axis aligned ...
0
votes
1
answer
70
views
can similarity transformation be linear transformation?
Learning Computer Graphics -
Can similarity transformation be linear transformation?
Similarity T is a rigid transformation (translation and rotations) with uniform scaling.
so I guess a similarity ...
1
vote
1
answer
459
views
Index variable takes up log(n) space?
In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits."
How does an array index ...
2
votes
1
answer
2k
views
what will be space complexity for snippet for(i=1 to n) int x=10;?
The space complexity of the code snippet given below:
...
1
vote
1
answer
95
views
The space complexity of a function that allocates space based on the input value and not size
What is the space complexity of the following hyphotetical function:
void function(int n) {
int[] array = new int[n]; // allocate array of size n
return;
}
...
3
votes
1
answer
818
views
Worst Case Space Complexity of Merge Sort and Bubble Sort
I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(...
1
vote
0
answers
66
views
Is there a difference in space complexity between inner product of matrices to multiple of inner products where each containing one matrix at a time?
The book I am reading is suggesting the following:
Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(...
1
vote
1
answer
316
views
Big O space complexity of this isAnagram method
I'm currently debating with some friends what is the Big O space complexity of this isAnagram method:
...
3
votes
4
answers
5k
views
Chess Knight minimum moves to destination on an infinite board
There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm.
Here is ...
2
votes
1
answer
70
views
Is there a measure of space usage over time?
We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space.
However, I feel this does not capture the full story.
Say we ...
2
votes
1
answer
518
views
A* 8-puzzle problem worst case memory usage
We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem.
We have to answer the following question but I can't figure out what it ...
2
votes
1
answer
6k
views
Python: A doubt on time and space complexity on string slicing
This qns is from my school's exam paper.
Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase.
The ...
1
vote
2
answers
163
views
Space efficient data structure for subsets of [1:n]
Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search(...
0
votes
1
answer
1k
views
Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?
I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy
However I'm not quite convinced by the answers ...
0
votes
1
answer
743
views
What is the time and space complexity of Rete algorithm
I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, ...
30
votes
1
answer
11k
views
Does space complexity analysis usually include output space?
Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
1
vote
0
answers
621
views
How to calculate multibit trie storage size?
I wish to use a multi-bit trie structure for storing IPv4 forwarding information with a fixed stride width of 8 bits, I think this is also called a "radix of 8" (so for any IP prefix 4 levels will ...
0
votes
0
answers
27
views
Space complexity and recurrence equation of a recursive method [duplicate]
I recently had to do the assignment to determine the space complexity of methods similar to the following. I need to state the recurrence equation (line by line), derive the closed form and use that ...
2
votes
1
answer
84
views
What is the complexity to show this theorem?
Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1).
There is need to show that the sum of all regular expressions is either equal to ...
0
votes
1
answer
76
views
How large would a database containing perfect knowledge of chess be?
Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-...
0
votes
1
answer
889
views
Does array always have a wasted space of O(n)?
In this question it's stated that dynamic array wasted space is O(n). Here is the explanation why:
Because, when a dynamic array is full, its size is increased by some
factor ...
12
votes
3
answers
17k
views
Why is DFS considered to have $O(bm)$ space complexity?
According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space.
The same is ...
6
votes
1
answer
223
views
Memory needed for computational graph
Suppose we have a set of equations like this
p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f()
It can be represented by computational ...
0
votes
1
answer
3k
views
Why do depth-limited search algorithm and BFS have different memory complexity?
Let be $b$ the branching factor of the tree.
Let be $d$ the depth of the shallowest solution.
Let be $l$ the limit given to depth-limited search algorithm
Why is depth-limited search algorithm ...
7
votes
2
answers
2k
views
Space complexity of string indices: O(1) or O(log|S|)?
Say you have a string S and wish to store indices of it, e.g. letter at index 3 of "toast" is 'a'. Seems that people generally consider an index as taking ...
6
votes
1
answer
46
views
Showing strong connectivity is in DSPACE((logn)^2)
$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$
I've learned the following deterministic algorithm to solve the problem in $log^2n$ space:
$\psi(G,s,t,k) :$
$\hspace{1cm}\...
4
votes
1
answer
586
views
Is FKS hashing really linear space?
In FKS hashing, I wonder if the size of the table $G[1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability ...
2
votes
2
answers
4k
views
With Memoization Are Time Complexity & Space Complexity Always the Same?
I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
3
votes
1
answer
516
views
Recurrence: space complexity to Tournament Method
Tournament method have this structure to found min and max (function getMinMax):
...
0
votes
1
answer
57
views
Searching through all program of a stack-based language with little memory
I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.
Given a program fragment, I can ...
6
votes
1
answer
135
views
How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?
Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
3
votes
1
answer
147
views
Is the memory usage of total languages deterministic?
I'm interested in the memory usage of various programming languages when implemented on actual hardware.
I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
1
vote
2
answers
3k
views
How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?
The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time.
But in this case, we can't track actual shortest path with ...
0
votes
0
answers
137
views
Time complexity in relation to data size
Not sure if I completely understand this problem that was presented in class.
We were given function $$f(n) = 2*f(n-1) + n$$
The base case for all these functions $f(1)$ is equal to 1.
Assume $T(x)$ ...
4
votes
2
answers
6k
views
Space complexity of directed and undirected graph
I have started reading graph theory from Introduction to Algorithm. The author starts by saying that if the graph is dense then:
$$|E|\text{ close to }|V|^2$$ else if the graph is sparse then:
$$|E|\...
5
votes
3
answers
5k
views
Memory usage of a BST or hash table?
I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time.
1) What is the exact ...
2
votes
1
answer
814
views
Analysing Space Complexity
I have to compute the space complexity of this function:
...
5
votes
1
answer
2k
views
Since we need space for recursive calls, is the space complexity of the recursive factorial is n?
As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met:
In-place partitioning is used. This unstable partition requires O(1)
space.
After partitioning, the ...
2
votes
4
answers
3k
views
What is more important in an algorithm, small runtime or small memory usage?
I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type)...
0
votes
0
answers
22
views
Runtime and space usage of a snippet of code [duplicate]
I've been trying to understand time complexity and space complexity by writing my own snippets of code and solving them. Can you see if I'm correct?
...
1
vote
1
answer
51
views
Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?
Let $x,N$ be positive integers.
I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using $$\lceil\...
7
votes
1
answer
17k
views
Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?
I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain ...
1
vote
1
answer
288
views
Time/Space cost of Taxicab algorithm?
The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type ...